Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Dynamic Programming Revision
DSA

Dynamic Programming Revision

Quickly revise DP states, transitions, base cases, memoization, tabulation, and optimization.

Example: Min Cost Climbing Stairs

If cost is empty → return 0
If length == 1 → return cost[0]

prev2 = cost[0]
prev1 = cost[1]

For i from 2 to n-1:
    curr = cost[i] + min(prev1, prev2)
    prev2 = prev1
    prev1 = curr

Return min(prev1, prev2)

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

Edge Cases

  • n = 0
  • n = 1
  • Negative values (if allowed)
public int minCostClimbingStairs(int[] cost) {
    if (cost == null || cost.length == 0) return 0;
    if (cost.length == 1) return cost[0];

    int prev2 = cost[0];
    int prev1 = cost[1];

    for (int i = 2; i < cost.length; i++) {
        int curr = cost[i] + Math.min(prev1, prev2);
        prev2 = prev1;
        prev1 = curr;
    }

    return Math.min(prev1, prev2);
}
def minCostClimbingStairs(cost):
    if not cost:
        return 0
    if len(cost) == 1:
        return cost[0]

    prev2 = cost[0]
    prev1 = cost[1]

    for i in range(2, len(cost)):
        curr = cost[i] + min(prev1, prev2)
        prev2 = prev1
        prev1 = curr

    return min(prev1, prev2)
int minCostClimbingStairs(vector<int>& cost) {
    if (cost.empty()) return 0;
    if (cost.size() == 1) return cost[0];

    int prev2 = cost[0];
    int prev1 = cost[1];

    for (int i = 2; i < cost.size(); i++) {
        int curr = cost[i] + min(prev1, prev2);
        prev2 = prev1;
        prev1 = curr;
    }

    return min(prev1, prev2);
}
function minCostClimbingStairs(cost) {
  if (cost.length === 0) return 0;
  if (cost.length === 1) return cost[0];

  let prev2 = cost[0];
  let prev1 = cost[1];

  for (let i = 2; i < cost.length; i++) {
    const curr = cost[i] + Math.min(prev1, prev2);
    prev2 = prev1;
    prev1 = curr;
  }

  return Math.min(prev1, prev2);
}

2 2D DP (Grid – Min Path Sum)

Initialize dp[n][m]

dp[0][0] = grid[0][0]

Fill first row
Fill first column

For i in 1..n-1:
    For j in 1..m-1:
        dp[i][j] = grid[i][j] +
                   min(dp[i-1][j], dp[i][j-1])

Return dp[n-1][m-1]

Time: O(n × m) Space: O(n × m) → can optimize to O(m)

Edge Cases

  • Single row
  • Single column
  • Empty grid
public int minPathSum(int[][] grid) {
    int n = grid.length;
    int m = grid[0].length;

    int[][] dp = new int[n][m];
    dp[0][0] = grid[0][0];

    for (int i = 1; i < n; i++)
        dp[i][0] = dp[i - 1][0] + grid[i][0];

    for (int j = 1; j < m; j++)
        dp[0][j] = dp[0][j - 1] + grid[0][j];

    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = grid[i][j] +
                       Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[n - 1][m - 1];
}
def minPathSum(grid):
    n, m = len(grid), len(grid[0])

    dp = [[0] * m for _ in range(n)]
    dp[0][0] = grid[0][0]

    for i in range(1, n):
        dp[i][0] = dp[i - 1][0] + grid[i][0]

    for j in range(1, m):
        dp[0][j] = dp[0][j - 1] + grid[0][j]

    for i in range(1, n):
        for j in range(1, m):
            dp[i][j] = (
                grid[i][j]
                + min(dp[i - 1][j], dp[i][j - 1])
            )

    return dp[n - 1][m - 1]
int minPathSum(vector<vector<int>>& grid) {
    int n = grid.size();
    int m = grid[0].size();

    vector<vector<int>> dp(n, vector<int>(m));
    dp[0][0] = grid[0][0];

    for (int i = 1; i < n; i++)
        dp[i][0] = dp[i - 1][0] + grid[i][0];

    for (int j = 1; j < m; j++)
        dp[0][j] = dp[0][j - 1] + grid[0][j];

    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = grid[i][j] +
                       min(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[n - 1][m - 1];
}
function minPathSum(grid) {
  const n = grid.length;
  const m = grid[0].length;

  const dp = Array.from({ length: n }, () =>
    new Array(m).fill(0)
  );
  dp[0][0] = grid[0][0];

  for (let i = 1; i < n; i++)
    dp[i][0] = dp[i - 1][0] + grid[i][0];

  for (let j = 1; j < m; j++)
    dp[0][j] = dp[0][j - 1] + grid[0][j];

  for (let i = 1; i < n; i++) {
    for (let j = 1; j < m; j++) {
      dp[i][j] =
        grid[i][j] +
        Math.min(dp[i - 1][j], dp[i][j - 1]);
    }
  }

  return dp[n - 1][m - 1];
}

3 0/1 Knapsack (Space Optimized)

Initialize dp[0..W] = 0

For each item i:
    For w from W down to weight[i]:
        dp[w] = max(dp[w],
                    value[i] + dp[w-weight[i]])

Return dp[W]

Time: O(n × W) Space: O(W)

Must iterate backward to avoid reuse.

public int knapsack(int[] weight, int[] value, int W) {
    int[] dp = new int[W + 1];

    for (int i = 0; i < weight.length; i++) {
        for (int w = W; w >= weight[i]; w--) {
            dp[w] = Math.max(dp[w],
                     value[i] + dp[w - weight[i]]);
        }
    }
    return dp[W];
}
def knapsack(weight, value, W):
    dp = [0] * (W + 1)

    for i in range(len(weight)):
        for w in range(W, weight[i] - 1, -1):
            dp[w] = max(
                dp[w],
                value[i] + dp[w - weight[i]]
            )

    return dp[W]
int knapsack(vector<int>& weight, vector<int>& value, int W) {
    vector<int> dp(W + 1, 0);

    for (int i = 0; i < weight.size(); i++) {
        for (int w = W; w >= weight[i]; w--) {
            dp[w] = max(dp[w],
                        value[i] + dp[w - weight[i]]);
        }
    }
    return dp[W];
}
function knapsack(weight, value, W) {
  const dp = new Array(W + 1).fill(0);

  for (let i = 0; i < weight.length; i++) {
    for (let w = W; w >= weight[i]; w--) {
      dp[w] = Math.max(
        dp[w],
        value[i] + dp[w - weight[i]]
      );
    }
  }
  return dp[W];
}

4 Unbounded Knapsack

Initialize dp[0..W] = 0

For each item i:
    For w from weight[i] to W:
        dp[w] = max(dp[w],
                    value[i] + dp[w-weight[i]])

Return dp[W]

Difference: Forward iteration allows reuse.

public int unboundedKnapsack(int[] weight, int[] value, int W) {
    int[] dp = new int[W + 1];

    for (int i = 0; i < weight.length; i++) {
        for (int w = weight[i]; w <= W; w++) {
            dp[w] = Math.max(dp[w],
                     value[i] + dp[w - weight[i]]);
        }
    }
    return dp[W];
}
def unboundedKnapsack(weight, value, W):
    dp = [0] * (W + 1)

    for i in range(len(weight)):
        for w in range(weight[i], W + 1):
            dp[w] = max(
                dp[w],
                value[i] + dp[w - weight[i]]
            )

    return dp[W]
int unboundedKnapsack(vector<int>& weight, vector<int>& value, int W) {
    vector<int> dp(W + 1, 0);

    for (int i = 0; i < weight.size(); i++) {
        for (int w = weight[i]; w <= W; w++) {
            dp[w] = max(dp[w],
                        value[i] + dp[w - weight[i]]);
        }
    }
    return dp[W];
}
function unboundedKnapsack(weight, value, W) {
  const dp = new Array(W + 1).fill(0);

  for (let i = 0; i < weight.length; i++) {
    for (let w = weight[i]; w <= W; w++) {
      dp[w] = Math.max(
        dp[w],
        value[i] + dp[w - weight[i]]
      );
    }
  }
  return dp[W];
}

5 Longest Increasing Subsequence

Initialize dp[i] = 1

For i in 1..n-1:
    For j in 0..i-1:
        If arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j] + 1)

Return max(dp)

Time: O(n²)

public int lengthOfLIS(int[] nums) {
    if (nums.length == 0) return 0;

    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);

    int max = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}
def lengthOfLIS(nums):
    if not nums:
        return 0

    n = len(nums)
    dp = [1] * n

    max_len = 1

    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

        max_len = max(max_len, dp[i])

    return max_len
int lengthOfLIS(vector<int>& nums) {
    if (nums.empty()) return 0;

    int n = nums.size();
    vector<int> dp(n, 1);

    int maxLen = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }
    return maxLen;
}
function lengthOfLIS(nums) {
  if (nums.length === 0) return 0;

  const n = nums.length;
  const dp = new Array(n).fill(1);

  let max = 1;

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    max = Math.max(max, dp[i]);
  }
  return max;
}

6 Digit DP Skeleton

Function solve(pos, tight, state):
    If pos == length:
        return valid

    limit = digit[pos] if tight else 9

    For d in 0..limit:
        newTight = tight AND (d == limit)
        recurse

Memoize results
int[][][] dp;
String num;

public int count(String s) {
    num = s;
    dp = new int[20][2][100];

    for (int[][] layer : dp)
        for (int[] row : layer)
            Arrays.fill(row, -1);

    return solve(0, 1, 0);
}

private int solve(int pos, int tight, int sum) {
    if (pos == num.length())
        return 1;

    if (dp[pos][tight][sum] != -1)
        return dp[pos][tight][sum];

    int limit = (tight == 1)
                ? num.charAt(pos) - '0'
                : 9;

    int result = 0;

    for (int d = 0; d <= limit; d++) {
        int newTight = (tight == 1 && d == limit) ? 1 : 0;
        result += solve(pos + 1, newTight, sum + d);
    }

    return dp[pos][tight][sum] = result;
}
def count(s):
    from functools import lru_cache

    num = s

    @lru_cache(maxsize=None)
    def solve(pos, tight, sum_so_far):
        if pos == len(num):
            return 1

        limit = (
            int(num[pos]) if tight else 9
        )

        result = 0

        for d in range(limit + 1):
            new_tight = (
                1 if tight and d == limit else 0
            )
            result += solve(
                pos + 1,
                new_tight,
                sum_so_far + d
            )

        return result

    return solve(0, 1, 0)
int dp[20][2][100];
string num;

int solve(int pos, int tight, int sum) {
    if (pos == num.size())
        return 1;

    if (dp[pos][tight][sum] != -1)
        return dp[pos][tight][sum];

    int limit = (tight == 1)
                ? num[pos] - '0'
                : 9;

    int result = 0;

    for (int d = 0; d <= limit; d++) {
        int newTight = (tight == 1 && d == limit) ? 1 : 0;
        result += solve(pos + 1, newTight, sum + d);
    }

    return dp[pos][tight][sum] = result;
}

int count(string s) {
    num = s;
    memset(dp, -1, sizeof(dp));

    return solve(0, 1, 0);
}
function count(s) {
  const memo = new Map();

  function solve(pos, tight, sum) {
    if (pos === s.length) return 1;

    const key = `${pos},${tight},${sum}`;

    if (memo.has(key)) return memo.get(key);

    const limit = tight
      ? +s[pos]
      : 9;

    let result = 0;

    for (let d = 0; d <= limit; d++) {
      const newTight =
        tight && d === limit ? 1 : 0;

      result += solve(pos + 1, newTight, sum + d);
    }

    memo.set(key, result);
    return result;
  }

  return solve(0, 1, 0);
}

My Private Notes

Notes are auto-saved locally to this device.