Dynamic Programming Explained: Complete Guide with Examples

Dynamic programming (DP) is the technique that separates junior from senior engineers on interview whiteboards — and it's the source of the most efficient solutions for a huge class of real-world problems. Once you see the pattern, DP problems stop being magic and become mechanical. This guide teaches you how.

What is dynamic programming?

Dynamic programming is an algorithm design technique that solves problems by:

1. Breaking them into overlapping subproblems
2. Solving each subproblem once
3. Storing the result to avoid recomputation

The name was coined by Richard Bellman in the 1950s — "dynamic" was chosen partly for its impressive sound, not its technical meaning.

The key insight: if you can express the answer to a big problem in terms of answers to smaller problems, and those smaller problems repeat, DP gives you an exponential speedup.

DP vs divide and conquer

When does DP apply?

A problem is a DP candidate if it has both:

1. Optimal substructure — the optimal solution can be built from optimal solutions to subproblems
2. Overlapping subproblems — the same subproblems are solved multiple times in a naive recursive approach

Quick checklist

Ask yourself:

• "Find the minimum/maximum/count/longest/shortest..." → likely DP
• "How many ways to..." → likely DP (counting DP)
• "Is it possible to..." → likely DP (boolean DP)
• "What is the optimal..." → likely DP

Not DP (common confusion)

• Greedy problems look similar but each choice is locally optimal and never revisited
• Divide & conquer (quicksort, merge sort) splits into independent parts
• BFS/DFS for unweighted shortest path

Two approaches: top-down vs bottom-up

Top-down (memoization)

Write the natural recursion, then cache results. Called "top-down" because you start with the big problem and recurse down.

# Fibonacci — top-down with memoization
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(50))  # 12586269025 — instant

// Fibonacci — top-down with manual memo
function fib(n, memo = {}) {
    if (n in memo) return memo[n];
    if (n <= 1) return n;
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

Bottom-up (tabulation)

Fill a table iteratively, starting from base cases. Called "bottom-up" because you solve smallest subproblems first.

# Fibonacci — bottom-up tabulation
def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

# Space-optimized: only need last two values
def fib_optimized(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

// Fibonacci — bottom-up in Java
public int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// Fibonacci — bottom-up in Go
func fib(n int) int {
    if n <= 1 {
        return n
    }
    prev2, prev1 := 0, 1
    for i := 2; i <= n; i++ {
        prev2, prev1 = prev1, prev1+prev2
    }
    return prev1
}

Top-down vs bottom-up comparison

The DP framework: 4 steps

Every DP problem follows the same template:

1. Define the subproblem — what does dp[i] or dp[i][j] represent?
2. Write the recurrence — how does dp[i] relate to smaller subproblems?
3. Identify base cases — what are the trivially known values?
4. Determine order — in what order do you fill the table?

This is the hardest step: defining dp[i] precisely. Getting this wrong leads to wrong recurrences.

Classic DP problems

1. Climbing stairs (LeetCode 70)

Problem: n stairs, each step 1 or 2 steps. Count distinct ways to reach top.

Define: dp[i] = number of ways to reach stair i

Recurrence: dp[i] = dp[i-1] + dp[i-2] (come from one step back or two steps back)

Base cases: dp[1] = 1, dp[2] = 2

def climbStairs(n):
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

function climbStairs(n) {
    if (n <= 2) return n;
    let prev2 = 1, prev1 = 2;
    for (let i = 3; i <= n; i++) {
        [prev2, prev1] = [prev1, prev1 + prev2];
    }
    return prev1;
}

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

2. Coin change (LeetCode 322)

Problem: Given coin denominations and amount, find fewest coins to make amount. Return -1 if impossible.

Define: dp[i] = minimum coins to make amount i

Recurrence: dp[i] = min(dp[i - coin] + 1) for each coin ≤ i

Base cases: dp[0] = 0, rest = infinity

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

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

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

Complexity: O(amount × coins) time, O(amount) space

3. Longest common subsequence (LeetCode 1143)

Problem: Given two strings, find length of longest subsequence common to both.

Define: dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]

Recurrence:

• If text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
• Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Base cases: dp[0][j] = dp[i][0] = 0

def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

function longestCommonSubsequence(text1, text2) {
    const m = text1.length, n = text2.length;
    const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

Complexity: O(m×n) time and space

4. 0/1 Knapsack

Problem: n items with weights and values, knapsack capacity W. Maximize value without exceeding capacity. Each item used at most once.

Define: dp[i][w] = max value using first i items with capacity w

Recurrence:

• Skip item i: dp[i][w] = dp[i-1][w]
• Take item i (if weight[i] <= w): dp[i][w] = dp[i-1][w - weight[i]] + value[i]
• dp[i][w] = max(skip, take)

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]  # skip
            if weights[i - 1] <= w:
                take = dp[i - 1][w - weights[i - 1]] + values[i - 1]
                dp[i][w] = max(dp[i][w], take)
    return dp[n][W]

# Space-optimized (1D dp)
def knapsack_1d(weights, values, W):
    dp = [0] * (W + 1)
    for i in range(len(weights)):
        # traverse right to left to avoid using item twice
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

function knapsack(weights, values, W) {
    const n = weights.length;
    const dp = new Array(W + 1).fill(0);
    for (let i = 0; i < n; i++) {
        for (let w = W; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

Complexity: O(n×W) time, O(W) space (1D optimized)

5. Longest increasing subsequence (LeetCode 300)

Problem: Find length of longest strictly increasing subsequence.

DP approach — O(n²):

Define: dp[i] = length of LIS ending at index i

Recurrence: dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]

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

Optimized O(n log n) with patience sorting:

import bisect

def lengthOfLIS(nums):
    tails = []  # tails[i] = smallest tail element of all IS of length i+1
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)

function lengthOfLIS(nums) {
    const tails = [];
    for (const num of nums) {
        let lo = 0, hi = tails.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (tails[mid] < num) lo = mid + 1;
            else hi = mid;
        }
        tails[lo] = num;
    }
    return tails.length;
}

Complexity: O(n log n) time, O(n) space

6. Edit distance (LeetCode 72)

Problem: Minimum operations (insert, delete, replace) to convert word1 to word2.

Define: dp[i][j] = min edits to convert word1[0..i-1] to word2[0..j-1]

Recurrence:

• Same char: dp[i][j] = dp[i-1][j-1]
• Replace: dp[i][j] = dp[i-1][j-1] + 1
• Delete from word1: dp[i][j] = dp[i-1][j] + 1
• Insert into word1: dp[i][j] = dp[i][j-1] + 1
• dp[i][j] = min(replace, delete, insert) if chars differ

def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j - 1],  # replace
                    dp[i - 1][j],      # delete
                    dp[i][j - 1]       # insert
                )
    return dp[m][n]

func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
        dp[i][0] = i
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = 1 + min3(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[m][n]
}

func min3(a, b, c int) int {
    if a < b { b = a }
    if b < c { return b }
    return c
}

Complexity: O(m×n) time and space

7. House robber (LeetCode 198)

Problem: Rob houses in a row. Adjacent houses trigger alarm. Maximize amount robbed.

Define: dp[i] = max money robbing from first i houses

Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i])

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    prev2, prev1 = 0, 0
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1

function rob(nums) {
    let prev2 = 0, prev1 = 0;
    for (const num of nums) {
        [prev2, prev1] = [prev1, Math.max(prev1, prev2 + num)];
    }
    return prev1;
}

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

8. Unique paths (LeetCode 62)

Problem: Robot on m×n grid. Can only move right or down. Count paths from top-left to bottom-right.

Define: dp[i][j] = paths to reach cell (i, j)

Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1]

def uniquePaths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]

# Space-optimized: single row
def uniquePaths_opt(m, n):
    dp = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]
    return dp[n - 1]

function uniquePaths(m, n) {
    const dp = new Array(n).fill(1);
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}

Complexity: O(m×n) time, O(n) space

9. Partition equal subset sum (LeetCode 416)

Problem: Can array be partitioned into two subsets with equal sum?

Transform: If total sum is odd → false. Otherwise find subset summing to total/2. This is a 0/1 knapsack variant.

Define: dp[s] = true if subset with sum s exists

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = {0}
    for num in nums:
        dp = dp | {s + num for s in dp}
        if target in dp:
            return True
    return False

# Bitset approach (fast)
def canPartition_bitset(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    bits = 1  # bit i = 1 means sum i is achievable
    for num in nums:
        bits |= (bits << num)
    return bool(bits & (1 << 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 num of nums) {
        for (let s = target; s >= num; s--) {
            dp[s] = dp[s] || dp[s - num];
        }
    }
    return dp[target];
}

10. Maximum subarray (LeetCode 53) — Kadane's algorithm

Problem: Find contiguous subarray with largest sum.

Define: dp[i] = max subarray sum ending at index i

Recurrence: dp[i] = max(nums[i], dp[i-1] + nums[i])

def maxSubArray(nums):
    max_sum = curr = nums[0]
    for num in nums[1:]:
        curr = max(num, curr + num)
        max_sum = max(max_sum, curr)
    return max_sum

function maxSubArray(nums) {
    let maxSum = nums[0], curr = nums[0];
    for (let i = 1; i < nums.length; i++) {
        curr = Math.max(nums[i], curr + nums[i]);
        maxSum = Math.max(maxSum, curr);
    }
    return maxSum;
}

public int maxSubArray(int[] nums) {
    int maxSum = nums[0], curr = nums[0];
    for (int i = 1; i < nums.length; i++) {
        curr = Math.max(nums[i], curr + nums[i]);
        maxSum = Math.max(maxSum, curr);
    }
    return maxSum;
}

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

11. Word break (LeetCode 139)

Problem: Given string s and word dictionary, can s be segmented into dictionary words?

Define: dp[i] = true if s[0..i-1] can be segmented

Recurrence: dp[i] = true if any dp[j] == true and s[j..i-1] is in dict

def wordBreak(s, wordDict):
    word_set = set(wordDict)
    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 word_set:
                dp[i] = True
                break
    return dp[n]

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

12. Decode ways (LeetCode 91)

Problem: String of digits, A=1..Z=26. Count decodings.

Define: dp[i] = ways to decode s[0..i-1]

def numDecodings(s):
    if not s or s[0] == '0':
        return 0
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1 if s[0] != '0' else 0
    for i in range(2, n + 1):
        one_digit = int(s[i - 1])
        two_digits = int(s[i - 2:i])
        if 1 <= one_digit <= 9:
            dp[i] += dp[i - 1]
        if 10 <= two_digits <= 26:
            dp[i] += dp[i - 2]
    return dp[n]

function numDecodings(s) {
    if (!s || s[0] === '0') return 0;
    const n = s.length;
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = s[0] !== '0' ? 1 : 0;
    for (let i = 2; i <= n; i++) {
        const one = parseInt(s[i - 1]);
        const two = parseInt(s.slice(i - 2, i));
        if (one >= 1) dp[i] += dp[i - 1];
        if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
    }
    return dp[n];
}

13. Palindrome substrings (LeetCode 647)

Problem: Count palindromic substrings.

Approach: dp[i][j] = true if s[i..j] is palindrome.

def countSubstrings(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    count = 0
    # Every single char is palindrome
    for i in range(n):
        dp[i][i] = True
        count += 1
    # Two chars
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            count += 1
    # Longer substrings
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                count += 1
    return count

# Expand-around-center (O(n²) time, O(1) space)
def countSubstrings_expand(s):
    def expand(l, r):
        count = 0
        while l >= 0 and r < len(s) and s[l] == s[r]:
            count += 1
            l -= 1
            r += 1
        return count
    return sum(expand(i, i) + expand(i, i + 1) for i in range(len(s)))

14. Matrix chain multiplication

Problem: Minimize scalar multiplications to compute a chain of matrices.

Define: dp[i][j] = min multiplications to compute matrices i through j

Recurrence: dp[i][j] = min(dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j]) for all k in [i, j-1]

def matrixChain(dims):
    n = len(dims) - 1  # number of matrices
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n - 1]

15. Burst balloons (LeetCode 312)

Problem: n balloons, each with value. Burst all. When you burst balloon i, get nums[i-1]*nums[i]*nums[i+1] coins. Maximize coins.

Key insight: Think backwards — last balloon to burst in range [i,j].

Define: dp[i][j] = max coins from bursting all balloons in range (i, j) exclusive

def maxCoins(nums):
    nums = [1] + nums + [1]  # boundary balloons
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for left in range(n - length):
            right = left + length
            for k in range(left + 1, right):
                coins = nums[left] * nums[k] * nums[right]
                dp[left][right] = max(
                    dp[left][right],
                    dp[left][k] + coins + dp[k][right]
                )
    return dp[0][n - 1]

DP patterns and categories

State machine DP: stock trading

These problems have multiple states (holding/not holding, cooldown, transaction limit).

Best time to buy and sell stock II (LeetCode 122)

def maxProfit(prices):
    # States: cash (not holding), hold (holding)
    cash, hold = 0, -prices[0]
    for price in prices[1:]:
        cash = max(cash, hold + price)
        hold = max(hold, cash - price)
    return cash

With cooldown (LeetCode 309)

def maxProfit(prices):
    # States: held, sold (cooldown), rest
    held, sold, rest = -prices[0], 0, 0
    for price in prices[1:]:
        held = max(held, rest - price)
        sold = held + price
        rest = max(rest, sold)  # previous sold becomes rest
    # Wait: sold here is using OLD held, need temp
    # Correct version:
    held2, sold2, rest2 = -prices[0], 0, 0
    for price in prices[1:]:
        prev_held = held2
        held2 = max(held2, rest2 - price)
        rest2 = max(rest2, sold2)
        sold2 = prev_held + price
    return max(sold2, rest2)

Common mistakes and how to fix them

Space optimization patterns

1D optimization from 2D (when row only depends on previous row)

# Before: O(m*n) space
dp = [[0] * (n + 1) for _ in range(m + 1)]

# After: O(n) space — overwrite previous row
dp = [0] * (n + 1)
# Iterate i in outer loop, j in inner loop
# Use dp[j] (current) and dp[j-1] (left in same row)
# Previous row value: save before overwriting

Right-to-left for 0/1 decisions

In 0/1 knapsack, iterate capacity right-to-left to prevent using same item twice:

# WRONG: allows item reuse (unbounded knapsack behavior)
for w in range(weight, W + 1):
    dp[w] = max(dp[w], dp[w - weight] + value)

# CORRECT: 0/1 knapsack
for w in range(W, weight - 1, -1):
    dp[w] = max(dp[w], dp[w - weight] + value)

Interview strategy

How to approach a DP problem in an interview

1. Clarify — constraints, examples, edge cases
2. Brute force first — write naive recursion, explain why it's slow
3. Identify overlapping subproblems — draw recursion tree, show repeated work
4. Define state — say it out loud: "dp[i] represents..."
5. Write recurrence — derive from brute force
6. Handle base cases — smallest valid inputs
7. Implement top-down first — easier to derive
8. Optimize to bottom-up — if asked, convert
9. Space optimize — only if time permits

Time complexity analysis

For most 1D DP: O(n) states, O(1) work → O(n) total
For most 2D DP: O(m×n) states, O(1) work → O(m×n) total

Practice roadmap

Beginner (understand the concept)

1. Fibonacci number (509)
2. Climbing stairs (70)
3. House robber (198)
4. Maximum subarray (53)

Intermediate (standard patterns)

5. Coin change (322)
6. Unique paths (62)
7. Longest increasing subsequence (300)
8. Word break (139)
9. Decode ways (91)
10. Partition equal subset sum (416)

Advanced (2D DP)

11. Longest common subsequence (1143)
12. Edit distance (72)
13. Palindromic substrings (647)
14. Interleaving string (97)
15. Regular expression matching (10)

Expert (interval and bitmask DP)

16. Burst balloons (312)
17. Minimum cost to cut a stick (1547)
18. Palindrome partitioning II (132)
19. Shortest path visiting all nodes (847)
20. Number of ways to wear different hats (1434)

FAQ

Q: How do I know if a problem needs DP or greedy?

Greedy works when each locally optimal choice leads to a global optimum — you never need to reconsider. DP is required when you need to compare multiple choices at each step. If you can prove a greedy exchange argument, use greedy; otherwise, reach for DP.

Q: Top-down or bottom-up for interviews?

Top-down is easier to derive (just memoize your recursion). Bottom-up often has better constant factors and no stack overflow risk. In interviews, start top-down to get it working, then mention you'd optimize to bottom-up.

Q: Why does the 0/1 knapsack iterate right-to-left?

Because we only want to use each item once. If we iterated left-to-right and updated dp[w], then when we reach dp[w + weight], we'd see the updated dp[w] as if the item was already used — allowing it twice. Right-to-left ensures we only see the "before this item" values.

Q: What's the difference between LCS and LIS?

LCS (Longest Common Subsequence) compares two sequences: O(m×n). LIS (Longest Increasing Subsequence) finds longest increasing subsequence in one sequence: O(n²) with DP, O(n log n) with binary search + patience sorting.

Q: Can memoization cause stack overflow?

Yes, for deep recursion (e.g., n > 10,000 in Python with default recursion limit of 1000). Fix with sys.setrecursionlimit(), convert to bottom-up, or use an explicit stack.

Q: How do I handle "count the number of ways" vs "find minimum"?

For counting: dp[i] += dp[j] (sum all valid previous states). For optimization: dp[i] = min/max(dp[i], dp[j] + cost). The recurrence structure is the same; only the aggregation changes.