Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › DSA

Dynamic Programming

DP = recursion + remembering answers. If a recursive solution solves the same sub-problem again and again, store each answer once and reuse it.

A problem needs DP when it has:

  1. Optimal substructure — the best answer is built from best answers of smaller sub-problems.
  2. Overlapping sub-problems — the same sub-problems repeat.

Signal words: number of ways, minimum/maximum cost, longest/shortest, can we reach, choose or skip.

The 5-step recipe

  1. State — what parameters describe a sub-problem? (dp[i] = answer for the first i items)
  2. Transition — how does dp[i] come from smaller states?
  3. Base cases — the smallest states you know directly.
  4. Order — compute states before they are needed (or let recursion do it).
  5. Answer — which state is the final answer?

Memoisation vs tabulation — Fibonacci

// plain recursion: O(2ⁿ)
// 1) memoisation (top-down): O(n)
vector<long long> memo(91, -1);
long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

// 2) tabulation (bottom-up): O(n)
long long fibTab(int n) {
    if (n <= 1) return n;
    vector<long long> dp(n + 1);
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

// 3) space optimised: O(1) memory
long long fibO1(int n) {
    long long a = 0, b = 1;
    while (n--) { long long c = a + b; a = b; b = c; }
    return a;
}
Memoisation Tabulation
Style recursive, top-down loops, bottom-up
Easy to write from brute force ✅ needs the right loop order
Stack overflow risk yes (deep recursion) no
Space optimisation hard easy (keep only needed rows)

Interview tip: write the recursion first, add memoisation, then convert to tabulation if asked.

Family 1: 1D DP

Climbing stairs (1 or 2 steps): dp[i] = dp[i-1] + dp[i-2]. House robber (no two adjacent): dp[i] = max(dp[i-1], dp[i-2] + a[i]). Coin change (min coins):

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int x = 1; x <= amount; x++)
        for (int c : coins)
            if (c <= x && dp[x - c] != INT_MAX) dp[x] = min(dp[x], dp[x - c] + 1);
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

Family 2: grid DP

Unique paths (move right/down): dp[r][c] = dp[r-1][c] + dp[r][c-1]. Minimum path sum: dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]).

Family 3: 0/1 knapsack (take or skip)

dp[i][w] = best value using the first i items with capacity w.

int knapsack(vector<int>& wt, vector<int>& val, int W) {
    vector<int> dp(W + 1, 0);                    // 1D: loop w downwards so each item is used once
    for (int i = 0; i < wt.size(); i++)
        for (int w = W; w >= wt[i]; w--)
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
    return dp[W];
}

Same family: subset sum, partition equal subset sum, target sum. Unbounded knapsack (items reusable): loop w upwards.

Family 4: strings (two indices)

Longest Common Subsequence:

int lcs(string a, string b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = a[i-1] == b[j-1] ? dp[i-1][j-1] + 1 : max(dp[i-1][j], dp[i][j-1]);
    return dp[n][m];
}

Same family: edit distance, longest palindromic subsequence, shortest common supersequence, distinct subsequences.

Family 5: Longest Increasing Subsequence

dp[i] = LIS ending at i → O(n²). The binary search method (keep the smallest tail for each length) is O(n log n).

Family 6: intervals / partitions

dp[i][j] over a range: matrix chain multiplication, burst balloons, palindrome partitioning (min cuts). Loop by length of the range.

Family 7: DP on stocks

States: day + holding/not holding (+ transactions left, cooldown). Best time to buy and sell stock I–IV.

Complexity

Time ≈ number of states × work per transition. LCS: n·m states × O(1) = O(n·m).

Classic problems

Climbing stairs · House robber I/II · Coin change I/II · Unique paths · Minimum path sum · 0/1 knapsack · Partition equal subset sum · LCS · Edit distance · LIS · Word break · Decode ways · Longest palindromic substring · Matrix chain multiplication · Buy and sell stock.

Practise in the Dynamic Programming section.

Interview one-liners

More DSA notes