Dynamic Programming

Dynamic programming solves problems by breaking them into overlapping subproblems and storing intermediate results to avoid recomputation. There are two primary approaches: top-down (memoization) and bottom-up (tabulation).

Top-Down Approach (Memoization)

Start from the highest value n and recurse downward, caching results in a data structure — typically a hash map — to avoid recomputing the same subproblems:

#include <unordered_map>
using namespace std;
 
class Solution {
public:
    unordered_map<int, int> hashMap;
    Solution() {
        hashMap[1] = 1;
        hashMap[2] = 2;
    }
 
    int climbStairs(int n) {
        if (hashMap.count(n))
            return hashMap[n];
        hashMap[n] = climbStairs(n - 1) + climbStairs(n - 2);
        return hashMap[n];
    }
};

Time: O(n), Space: O(n) (recursion stack + cache).

Bottom-Up Approach (Tabulation)

Solve iteratively from smallest to largest index, retaining only the minimum state required for the next step. This eliminates recursion overhead and reduces memory:

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
 
        int one = 1, two = 2, ways = 0;
        for (int i = 3; i <= n; ++i) {
            ways = one + two;
            one = two;
            two = ways;
        }
        return ways;
    }
};

Time: O(n), Space: O(1).

Choosing Between Approaches

Aspect	Top-Down	Bottom-Up
Implementation	Recursive, intuitive	Iterative
Space	O(n) cache + call stack	O(1) to O(n) variables
When to use	Natural recursion, sparse states	Dense state space, memory pressure
Risk	Stack overflow for large n	Must order subproblem dependencies

Bottom-up should be preferred wherever possible for its memory efficiency and avoidance of recursion overhead.

References

• Dynamic Programming