Dynamic Programming

Top Down

Begin with the search of the final solution, breaking it down into further sub-problems

    f(n) = f(n) -> f(n-1) -> f(n-2)... f(1)

• Recursive
• More intuitive
• Stack hungry
• Usually 2^n branches - but optimized using memoization

Bottom Up

Begin with the sub-problem and build towards the final solution

    f(n) = f(1) -> f(2) ... f(n)

• Iterative
• Preferred due to low memory and lack of recursion

Forward

Subsequent solution is calculated from the previous solution(s)

dp[0] = 0;
dp[1] = 1;

for (int i = 2; i < n ; i++) {
    dp[i] = dp[i-1] + dp[i-2];     // Forward : i is calculated from i-1 and i-2
}

Backward

Previous solution(s) contribute to the subsequent solution

dp[0] = 0;
dp[1] = 1;

for (int i = 2; i < n ; i++) {
    dp[i+1] += dp[i]               // Backward : i is contributing to i+1 and i+2
    dp[i+2] += dp[i]
}