DSA · Lesson 14 of 17

Dynamic Programming (1-D)

⏱ 15 min🎬 Interactive visualizer💻 Python · Java · C++ · JavaScript🧩 7 practice problems

When a recursive solution recomputes the same subproblems, store them. Climbing stairs, house robber, coin change, word break and LIS, with the recurrence visualised.

What makes a problem “DP”?

Optimal substructure: the best answer is built from best answers to smaller subproblems.
Overlapping subproblems: plain recursion would solve the same subproblem many times.

Fibonacci by plain recursion is O(2ⁿ). Store each fib(i) once and it becomes O(n).

The 4-step recipe (say it out loud in interviews)

State: what does dp[i] mean, in words? (“the most money robbing houses 0..i”)
Recurrence: how does dp[i] depend on smaller states? (max(dp[i−1], dp[i−2] + a[i]))
Base cases: dp[0], dp[1], or the empty prefix.
Order and answer: fill from small to large; the answer is dp[n−1], or max(dp).

Then optimise space: if dp[i] only looks back a fixed number of steps, keep a few variables instead of an array.

Top-down or bottom-up?

Top-down (memoisation): write the recursion, cache results (@lru_cache in Python, a map or array elsewhere). Easy to derive.
Bottom-up (tabulation): fill an array in order. No recursion-depth issues, easy to optimise space.

Classic 1-D recurrences

Problem	dp[i] means	Recurrence
Climbing stairs	ways to reach step i	dp[i−1] + dp[i−2]
House robber	best loot up to house i	max(dp[i−1], dp[i−2] + a[i])
Coin change	fewest coins for amount i	1 + min(dp[i − c])
Word break	s[:i] can be split	any(dp[j] and s[j:i] in dict)
LIS	longest increasing subsequence ending at i	1 + max(dp[j]) for a[j] < a[i]
Max subarray (Kadane)	best sum ending at i	max(a[i], dp[i−1] + a[i])

Code template

from functools import lru_cache

# Top-down: memoised recursion
def climb(n):
    @lru_cache(maxsize=None)
    def ways(i):
        if i <= 1: return 1
        return ways(i - 1) + ways(i - 2)
    return ways(n)

# Bottom-up with O(1) space
def rob(nums):
    prev, curr = 0, 0
    for x in nums:
        prev, curr = curr, max(curr, prev + x)
    return curr

# Unbounded choice per state
def coin_change(coins, amount):
    dp = [0] + [float('inf')] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a: dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

// Top-down: memoised recursion
long[] memo = new long[100];
long ways(int i) {
    if (i <= 1) return 1;
    if (memo[i] != 0) return memo[i];
    return memo[i] = ways(i - 1) + ways(i - 2);
}

// Bottom-up with O(1) space
int rob(int[] nums) {
    int prev = 0, curr = 0;
    for (int x : nums) { int next = Math.max(curr, prev + x); prev = curr; curr = next; }
    return curr;
}

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

// Top-down: memoised recursion
unordered_map<int, long long> memo;
long long ways(int i) {
    if (i <= 1) return 1;
    if (memo.count(i)) return memo[i];
    return memo[i] = ways(i - 1) + ways(i - 2);
}

// Bottom-up with O(1) space
int rob(const vector<int>& nums) {
    int prev = 0, curr = 0;
    for (int x : nums) { int next = max(curr, prev + x); prev = curr; curr = next; }
    return curr;
}

// Unbounded choice per state
int coinChange(const vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1); dp[0] = 0;
    for (int a = 1; a <= amount; a++) for (int c : coins) if (c <= a) dp[a] = min(dp[a], dp[a - c] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

// Top-down: memoised recursion
function climb(n, memo = new Map()) {
  if (n <= 1) return 1;
  if (!memo.has(n)) memo.set(n, climb(n - 1, memo) + climb(n - 2, memo));
  return memo.get(n);
}

// Bottom-up with O(1) space
function rob(nums) {
  let prev = 0, curr = 0;
  for (const x of nums) [prev, curr] = [curr, Math.max(curr, prev + x)];
  return curr;
}

// Unbounded choice per state
function coinChange(coins, amount) {
  const dp = [0, ...new Array(amount).fill(Infinity)];
  for (let a = 1; a <= amount; a++) for (const c of coins) if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Practise this pattern (7 problems)

Each problem has a statement, hints, approaches, solutions in 4 languages and a code runner. Solve them in order: easy first.

#	Problem	Difficulty
70	Climbing Stairs	Easy
71	House Robber	Medium
72	Coin Change	Medium
73	Longest Increasing Subsequence	Medium
74	Word Break	Medium
75	Maximum Subarray	Medium
76	Decode Ways	Medium

Common mistakes

Starting to code before defining the state in words.
Greedy instead of DP: coin change with coins [1, 3, 4] and amount 6, where greedy gives 4+1+1 but the optimum is 3+3.
Wrong base case (an empty string or amount 0).

Check yourself: what is dp for coins [2, 5] at amounts 0..6?

[0, ∞, 1, ∞, 2, 1, 3]. Amount 6 = 2 + 2 + 2.

🧩 All DSA problems 🎬 Algorithm visualizer 🎓 Certificates

Created by Ajeetkumar