Navigation

DSA dynamic programming 12 min read

Dynamic Programming Exercises: Answer Sheet & Worked Solutions

This is the answer sheet for the dynamic programming exercises. Each solution gives the key idea, the optimal complexity, the code in all four languages (use the switcher), and a common pitfall. Try the problems first — then check your work here.

Q1. Min Cost Climbing Stairs

Idea: Let dp[i] be the minimum cost to reach stair i (the top is index n). To stand on i you arrived from i-1 or i-2, paying that stair’s cost: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). Base cases dp[0] = dp[1] = 0 (free to start at either). Keep just two rolling variables.

Complexity: O(n) time, O(1) space.

int minCostClimbingStairs(const std::vector<int>& cost) {
    int n = cost.size();
    int a = 0, b = 0;                       // dp[i-2], dp[i-1]
    for (int i = 2; i <= n; i++) {
        int cur = std::min(b + cost[i - 1], a + cost[i - 2]);
        a = b; b = cur;
    }
    return b;                               // dp[n]
}

int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int a = 0, b = 0;                       // dp[i-2], dp[i-1]
    for (int i = 2; i <= n; i++) {
        int cur = Math.min(b + cost[i - 1], a + cost[i - 2]);
        a = b; b = cur;
    }
    return b;                               // dp[n]
}

function minCostClimbingStairs(cost) {
  const n = cost.length;
  let a = 0, b = 0;                         // dp[i-2], dp[i-1]
  for (let i = 2; i <= n; i++) {
    const cur = Math.min(b + cost[i - 1], a + cost[i - 2]);
    a = b; b = cur;
  }
  return b;                                 // dp[n]
}

def min_cost_climbing_stairs(cost):
    n = len(cost)
    a, b = 0, 0                             # dp[i-2], dp[i-1]
    for i in range(2, n + 1):
        cur = min(b + cost[i - 1], a + cost[i - 2])
        a, b = b, cur
    return b                                # dp[n]

Pitfall: The “top” is one step past the last stair (index n), not the last stair itself. Returning dp[n-1] stops one stair early.

Q2. House Robber

Idea: At each house decide: skip it (keep the best so far) or rob it (its value plus the best up to two houses back). dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Two rolling variables suffice.

Complexity: O(n) time, O(1) space.

int rob(const std::vector<int>& nums) {
    int prev2 = 0, prev1 = 0;               // best up to i-2, i-1
    for (int x : nums) {
        int cur = std::max(prev1, prev2 + x);
        prev2 = prev1; prev1 = cur;
    }
    return prev1;
}

int rob(int[] nums) {
    int prev2 = 0, prev1 = 0;               // best up to i-2, i-1
    for (int x : nums) {
        int cur = Math.max(prev1, prev2 + x);
        prev2 = prev1; prev1 = cur;
    }
    return prev1;
}

function rob(nums) {
  let prev2 = 0, prev1 = 0;                 // best up to i-2, i-1
  for (const x of nums) {
    const cur = Math.max(prev1, prev2 + x);
    prev2 = prev1; prev1 = cur;
  }
  return prev1;
}

def rob(nums):
    prev2, prev1 = 0, 0                     # best up to i-2, i-1
    for x in nums:
        cur = max(prev1, prev2 + x)
        prev2, prev1 = prev1, cur
    return prev1

Pitfall: Updating prev2 and prev1 in the wrong order corrupts the state. Compute cur first, then shift.

Q3. Partition Equal Subset Sum

Idea: Two equal halves means each sums to total/2. If total is odd, it’s impossible. Otherwise this is subset sum to target = total/2: a boolean DP where dp[s] means “some subset reaches sum s.” Iterate sums downward so each number is used at most once (the 0/1 knapsack trick).

Complexity: O(n·S) time, O(S) space, where S is the total sum.

bool canPartition(const std::vector<int>& nums) {
    int total = 0;
    for (int x : nums) total += x;
    if (total % 2 != 0) return false;
    int target = total / 2;
    std::vector<char> dp(target + 1, false);
    dp[0] = true;
    for (int x : nums)
        for (int s = target; s >= x; s--)
            if (dp[s - x]) dp[s] = true;
    return dp[target];
}

boolean canPartition(int[] nums) {
    int total = 0;
    for (int x : nums) total += x;
    if (total % 2 != 0) return false;
    int target = total / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    for (int x : nums)
        for (int s = target; s >= x; s--)
            if (dp[s - x]) dp[s] = true;
    return dp[target];
}

function canPartition(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;
  const target = total / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
  for (const x of nums)
    for (let s = target; s >= x; s--)
      if (dp[s - x]) dp[s] = true;
  return dp[target];
}

def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for x in nums:
        for s in range(target, x - 1, -1):
            if dp[s - x]:
                dp[s] = True
    return dp[target]

Pitfall: Iterating sums forward lets a single number be counted multiple times, wrongly returning true. The reverse loop enforces “each element once.”

Q4. Longest Palindromic Subsequence

Idea: Interval DP. dp[i][j] = length of the longest palindromic subsequence within s[i..j]. If the ends match, they wrap a smaller palindrome: dp[i][j] = 2 + dp[i+1][j-1]. Otherwise drop one end: dp[i][j] = max(dp[i+1][j], dp[i][j-1]). Single characters give dp[i][i] = 1. Iterate i descending so inner intervals are ready.

Complexity: O(n²) time, O(n²) space.

int longestPalindromeSubseq(const std::string& s) {
    int n = s.size();
    std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++)
            dp[i][j] = (s[i] == s[j]) ? 2 + dp[i + 1][j - 1]
                                      : std::max(dp[i + 1][j], dp[i][j - 1]);
    }
    return n == 0 ? 0 : dp[0][n - 1];
}

int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++)
            dp[i][j] = (s.charAt(i) == s.charAt(j)) ? 2 + dp[i + 1][j - 1]
                       : Math.max(dp[i + 1][j], dp[i][j - 1]);
    }
    return n == 0 ? 0 : dp[0][n - 1];
}

function longestPalindromeSubseq(s) {
  const n = s.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let i = n - 1; i >= 0; i--) {
    dp[i][i] = 1;
    for (let j = i + 1; j < n; j++)
      dp[i][j] = s[i] === s[j] ? 2 + dp[i + 1][j - 1]
                 : Math.max(dp[i + 1][j], dp[i][j - 1]);
  }
  return n === 0 ? 0 : dp[0][n - 1];
}

def longest_palindrome_subseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        dp[i][i] = 1
        for j in range(i + 1, n):
            dp[i][j] = (2 + dp[i + 1][j - 1] if s[i] == s[j]
                        else max(dp[i + 1][j], dp[i][j - 1]))
    return 0 if n == 0 else dp[0][n - 1]

Pitfall: This is a subsequence, not a substring — don’t reset to 0 on a mismatch. (An equivalent solution is the LCS of s and its reverse.)

Q5. Coin Change (minimum coins)

Idea: dp[x] = fewest coins to make amount x. Initialize to “infinity,” set dp[0] = 0, and for each amount try every coin: dp[x] = min(dp[x], dp[x - c] + 1). If dp[amount] stays infinite, return -1. Unlimited coin reuse, so the inner amount loop runs forward.

Complexity: O(amount · coins) time, O(amount) space.

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

int coinChange(int[] coins, int amount) {
    int INF = amount + 1;
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, INF);
    dp[0] = 0;
    for (int x = 1; x <= amount; x++)
        for (int c : coins)
            if (c <= x) dp[x] = Math.min(dp[x], dp[x - c] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

function coinChange(coins, amount) {
  const INF = amount + 1;
  const dp = new Array(amount + 1).fill(INF);
  dp[0] = 0;
  for (let x = 1; x <= amount; x++)
    for (const c of coins)
      if (c <= x) dp[x] = Math.min(dp[x], dp[x - c] + 1);
  return dp[amount] > amount ? -1 : dp[amount];
}

def coin_change(coins, amount):
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x:
                dp[x] = min(dp[x], dp[x - c] + 1)
    return -1 if dp[amount] > amount else dp[amount]

Pitfall: Greedy (always grab the largest coin) is wrong in general — e.g. coins [1,3,4], amount 6 needs 3+3 (2 coins), not 4+1+1 (3). Full coverage in coin change.

Q6. Word Break

Idea: dp[i] = “can the first i characters be segmented?” It’s true if there’s a split point j where dp[j] is true and the substring s[j..i] is a dictionary word. Base case dp[0] = true (empty prefix). Use a hash set for O(1) word lookups.

Complexity: O(n²) splits × substring/lookup cost, O(n) space (plus the set).

bool wordBreak(const std::string& s, const std::vector<std::string>& words) {
    std::unordered_set<std::string> dict(words.begin(), words.end());
    int n = s.size();
    std::vector<char> dp(n + 1, false);
    dp[0] = true;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++)
            if (dp[j] && dict.count(s.substr(j, i - j))) { dp[i] = true; break; }
    return dp[n];
}

boolean wordBreak(String s, List<String> words) {
    Set<String> dict = new HashSet<>(words);
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++)
            if (dp[j] && dict.contains(s.substring(j, i))) { dp[i] = true; break; }
    return dp[n];
}

function wordBreak(s, words) {
  const dict = new Set(words);
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= n; i++)
    for (let j = 0; j < i; j++)
      if (dp[j] && dict.has(s.slice(j, i))) { dp[i] = true; break; }
  return dp[n];
}

def word_break(s, words):
    dict_set = set(words)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in dict_set:
                dp[i] = True
                break
    return dp[n]

Pitfall: Forgetting dp[0] = true makes every prefix unsegmentable — the first word never finds a valid split point to build on.

Q7. Maximum Product Subarray

Idea: Unlike sums, a negative times a negative can become the new maximum — so track both the running max and the running min ending at each index. When the current number is negative, the roles swap, so exchange max and min before updating. The answer is the best max seen.

Complexity: O(n) time, O(1) space.

int maxProduct(const std::vector<int>& a) {
    int best = a[0], curMax = a[0], curMin = a[0];
    for (int i = 1; i < (int)a.size(); i++) {
        int x = a[i];
        if (x < 0) std::swap(curMax, curMin);
        curMax = std::max(x, curMax * x);
        curMin = std::min(x, curMin * x);
        best = std::max(best, curMax);
    }
    return best;
}

int maxProduct(int[] a) {
    int best = a[0], curMax = a[0], curMin = a[0];
    for (int i = 1; i < a.length; i++) {
        int x = a[i];
        if (x < 0) { int t = curMax; curMax = curMin; curMin = t; }
        curMax = Math.max(x, curMax * x);
        curMin = Math.min(x, curMin * x);
        best = Math.max(best, curMax);
    }
    return best;
}

function maxProduct(a) {
  let best = a[0], curMax = a[0], curMin = a[0];
  for (let i = 1; i < a.length; i++) {
    const x = a[i];
    if (x < 0) [curMax, curMin] = [curMin, curMax];
    curMax = Math.max(x, curMax * x);
    curMin = Math.min(x, curMin * x);
    best = Math.max(best, curMax);
  }
  return best;
}

def max_product(a):
    best = cur_max = cur_min = a[0]
    for x in a[1:]:
        if x < 0:
            cur_max, cur_min = cur_min, cur_max
        cur_max = max(x, cur_max * x)
        cur_min = min(x, cur_min * x)
        best = max(best, cur_max)
    return best

Pitfall: Tracking only the max fails on [-2, 3, -4] — the answer 24 comes from multiplying two negatives. You must carry the running minimum too.

That’s the full answer sheet. Back to the DP exercises or explore the broader dynamic programming patterns.