Guide to Dynamic Programming - I will show the coding result.

Problem: given n, find the number of different ways to write n as the sum of 1, 3, 4

I conclude the method as 4 step solver.

Step 1. Define:
D[n] = number of ways to reach the sum n.

2. Recurrence:
D[n] = D[n - 1] + D[n - 3] + D[n - 4]

3. Base Case
D[0] = 1, D[1] = 1, D[2] = 1, D[3] = 2;
D[negative] = 0,

4. Result Case
D[n]

Time Complexity: O(n * m) - two for loops with n, m length; n is the sum; m is the length of that numbers array.
Space: O(n) - the whole D array

ok, now let's get hands dirty.


Result: [1, 1, 1, 2, 4, 6]
16:09:04:591 [main] INFO com.StandfordDP.Dynamic1 - 6


Reference: http://web.stanford.edu/class/cs97si/04-dynamic-programming.pdf