Given coins of different denominations and a total amount of money, find the number of combinations that makes up that amount. ​For example, given unlimited coins in 1, 2, 4 denominations, how many combinations are there to make up the amount of 12?

Given coins in different denominations, we'd solve this problem by breaking it into sub-problems which means given coins in less different denominations. The answer to the problem of given coins in n different denominations is based on solving the problem of given coins in (n-1) different denominations, and the answer to the problem of coins in (n-1) different denominations is based on solving the problem of coins in (n-2) different denominations.

We can use an array named combination to store the number of combinations that make up the amount. For example, the number of combinations to make up the amount of 1 is stored combination[1], and the combinations to make up the amount of 12 is stored in combination [12].

The number of combinations to make up a given amount is equal to the number of combinations before a coin denomination is added to the picture, plus the number of combinations after such a coin denomination is added to the picture for the amount of "amount - coin". 

When adding the first coin to the picture, we'd calculate this array - combination. When adding the 2nd coin to the picture, the same combination[amount] is being calculated based on the following pseudocode:   

There is a wall of size 4xN. You have infinite supply of bricks of size 4x1 and 1x4 in the house. How many ways are there to fill out a wall of size 4xN?

This can be addressed by dynamic programming. The characteristics of optimal substructure, recursive nature, and bottom-up approach were mentioned in this post. 

Let's say, number of ways to fill out a wall of size 4xN with infinite supply of 4x1 and 1x4 bricks is said to be f(N). Per common sense, we know:

f(1) = 1
f(2) = 1
f(3) = 1
f(4) = 2

Also, when you think about it when filling out 4xN with f(N) ways of doing it, you can break f(N), when N >= 4, down to 2 substructures as below. Given the fact that one 4x1 can goes either horizontally or vertically. When it goes horizontally, there's only one way as shown in f(N-1). But when it goes vertically, all other 3 bricks may need to go vertically as well as seen in f(N-4) below.

Given an array with integers, find the largest sum of continuous subarray. This maximum subarray problem was first posed in 1977. Jay Kadane solved it in linear time (O(n)) in 1988.