DSA Part 15: Core DP Patterns

1. Introduction and Motivation

Once you can derive a DP recurrence from first principles, the next skill is pattern recognition: most problems you will meet are a small number of recurring shapes wearing different clothing. DP problems fall into recognizable families based on the shape of their state space. 1D DP uses a single variable (array index, amount remaining, step count). 2D DP uses two variables (two string indices, grid coordinates, item × capacity). Recognizing the pattern lets you define the recurrence immediately.

2. Prerequisites

This lesson assumes you have already worked through Part 14: Dynamic Programming Foundations, where the discipline of turning a recursive brute force into a defined state, a recurrence, and a base case is built from first principles. Nothing here re-derives that methodology from scratch — each problem below states its dp definition and transition directly and moves straight into implementation.

If a recurrence below does not immediately make sense, that is the signal to go back to Part 14 and re-walk the state-design steps, rather than to memorize the code in front of you.

3. 1D DP: Climbing Stairs

You can climb 1 or 2 steps at a time. How many distinct ways to reach step $n$? This is structurally identical to Fibonacci: $dp[i] = dp[i-1] + dp[i-2]$. The "number of ways" at each step is the sum of ways to reach it from one step below (1 step) and two steps below (2 steps). State: $dp[i]$ = ways to reach step $i$. Transition: $dp[i] = dp[i-1] + dp[i-2]$. Base: $dp[0]=1, dp[1]=1$.

def climb_stairs(n):
    """
    LeetCode 70: Climbing Stairs
    Ways to reach top climbing 1 or 2 steps at a time
    Time: O(n), Space: O(1)
    """
    if n <= 2:
        return n

    prev2, prev1 = 1, 2

    for i in range(3, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr

    return prev1

# Example
for n in [2, 3, 4, 5]:
    print(f"Ways to climb {n} stairs: {climb_stairs(n)}")

// LeetCode 70: Climbing Stairs
// Time: O(n), Space: O(1)

class ClimbStairs {
public:
    static int climbStairs(int n) {
        if (n <= 2) return n;

        int prev2 = 1, prev1 = 2;
        for (int i = 3; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
};

// LeetCode 70: Climbing Stairs
// Time: O(n), Space: O(1)

class ClimbStairs {
    public static int climbStairs(int n) {
        if (n <= 2) return n;

        int prev2 = 1, prev1 = 2;
        for (int i = 3; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}

1D DP: Kadane's Algorithm and Min-Cost Climbing Stairs

Kadane's Algorithm (Maximum Subarray Sum)

Given an integer array, find the contiguous subarray with the largest sum. Every subarray ending at index $i$ either extends the best subarray ending at $i-1$, or starts fresh at $i$ — and once the running sum goes negative, dragging it forward can only shrink whatever comes next. State: $dp[i]$ = maximum sum of a subarray ending at index $i$. Transition: $dp[i] = \max(nums[i],\; dp[i-1] + nums[i])$. Base: $dp[0] = nums[0]$. Only $dp[i-1]$ is ever read, so the array collapses to a single rolling variable: $O(n)$ time, $O(1)$ space. The insight worth internalizing: whenever the running sum $dp[i-1]$ is negative, reset it to $nums[i]$ rather than carry the negative baggage forward — a negative prefix can never help a future sum, only hurt it.

As a slightly harder follow-up, the implementation below also tracks the start and end indices of the maximizing subarray itself, not just its sum — that means remembering where the current run began and only moving that marker forward on a reset, never on an ordinary extension.

def max_subarray(nums):
    """
    LeetCode 53: Maximum Subarray (Kadane's Algorithm)
    Returns (max_sum, start_index, end_index) of the maximizing subarray
    Time: O(n), Space: O(1)
    """
    max_sum = curr_sum = nums[0]
    start = best_start = best_end = 0

    for i in range(1, len(nums)):
        if curr_sum < 0:
            curr_sum = nums[i]
            start = i
        else:
            curr_sum += nums[i]

        if curr_sum > max_sum:
            max_sum = curr_sum
            best_start = start
            best_end = i

    return max_sum, best_start, best_end

# Example
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum, start, end = max_subarray(nums)
print(f"Array: {nums}")
print(f"Max subarray sum: {max_sum}, subarray: {nums[start:end+1]}")  # 6, [4, -1, 2, 1]

// LeetCode 53: Maximum Subarray (Kadane's Algorithm)
// Time: O(n), Space: O(1)
#include <vector>
#include <tuple>

class MaxSubarray {
public:
    static std::tuple<int, int, int> maxSubarray(std::vector<int>& nums) {
        int maxSum = nums[0], currSum = nums[0];
        int start = 0, bestStart = 0, bestEnd = 0;

        for (int i = 1; i < nums.size(); i++) {
            if (currSum < 0) {
                currSum = nums[i];
                start = i;
            } else {
                currSum += nums[i];
            }

            if (currSum > maxSum) {
                maxSum = currSum;
                bestStart = start;
                bestEnd = i;
            }
        }
        return {maxSum, bestStart, bestEnd};
    }
};

// LeetCode 53: Maximum Subarray (Kadane's Algorithm)
// Time: O(n), Space: O(1)

class MaxSubarray {
    public static int[] maxSubarray(int[] nums) {
        int maxSum = nums[0], currSum = nums[0];
        int start = 0, bestStart = 0, bestEnd = 0;

        for (int i = 1; i < nums.length; i++) {
            if (currSum < 0) {
                currSum = nums[i];
                start = i;
            } else {
                currSum += nums[i];
            }

            if (currSum > maxSum) {
                maxSum = currSum;
                bestStart = start;
                bestEnd = i;
            }
        }
        // {maxSum, bestStart, bestEnd}
        return new int[]{maxSum, bestStart, bestEnd};
    }
}

Min-Cost Climbing Stairs

Section 9's Exercises and Mastery posed Min Cost Climbing Stairs (LeetCode 746) as a conceptual exercise: adapt the Climbing Stairs recurrence so each transition also pays a cost, then re-check the base cases. Here is that recurrence carried through to a full implementation. Each step $i$ carries a cost to leave it, and you may start standing on step 0 or step 1 for free; from there you always pay the cost of whichever step you leave. State: $dp[i]$ = minimum cost to reach step $i$. Transition: $dp[i] = cost[i] + \min(dp[i-1], dp[i-2])$. Base: $dp[0] = cost[0]$, $dp[1] = cost[1]$. The top of the staircase is one step past the last index, so the answer is $\min(dp[n-1], dp[n-2])$ — whichever of the last two steps is cheaper to leave from. Time: $O(n)$, Space: $O(1)$ once rolled to two variables, exactly like Climbing Stairs itself.

def min_cost_climbing_stairs(cost):
    """
    LeetCode 746: Min Cost Climbing Stairs
    dp[i] = minimum cost to reach step i; you may start at step 0 or step 1
    Time: O(n), Space: O(1)
    """
    n = len(cost)
    prev2, prev1 = cost[0], cost[1]

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

    return min(prev1, prev2)

# Example
cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
print(f"Costs: {cost}")
print(f"Min cost to reach top: {min_cost_climbing_stairs(cost)}")  # 6

// LeetCode 746: Min Cost Climbing Stairs
// Time: O(n), Space: O(1)
#include <vector>
#include <algorithm>

class MinCostClimbingStairs {
public:
    static int minCostClimbingStairs(std::vector<int>& cost) {
        int n = cost.size();
        int prev2 = cost[0], prev1 = cost[1];

        for (int i = 2; i < n; i++) {
            int curr = cost[i] + std::min(prev1, prev2);
            prev2 = prev1;
            prev1 = curr;
        }
        return std::min(prev1, prev2);
    }
};

// LeetCode 746: Min Cost Climbing Stairs
// Time: O(n), Space: O(1)

class MinCostClimbingStairs {
    public static int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int prev2 = cost[0], prev1 = cost[1];

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

4. 1D DP: House Robber

Given an array of house values where adjacent houses cannot both be robbed (they trigger an alarm), maximize total loot. This is the classic "include/exclude" DP pattern: at each house $i$, you either rob it (adding its value to the best from $i-2$) or skip it (carrying forward the best from $i-1$). State: $dp[i]$ = max loot from houses $0..i$. Transition: $dp[i] = \max(dp[i-1],\; dp[i-2] + nums[i])$. This pattern appears in many variants: circular houses (LeetCode 213), binary tree robber (LeetCode 337).

def house_robber(nums):
    """
    LeetCode 198: House Robber
    Max money robbing non-adjacent houses
    Time: O(n), Space: O(1)
    """
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    # dp[i] = max(rob this house + dp[i-2], skip this house + dp[i-1])
    prev2 = nums[0]
    prev1 = max(nums[0], nums[1])

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

    return prev1

# Example
houses = [2, 7, 9, 3, 1]
print(f"Houses: {houses}")
print(f"Max robbery: {house_robber(houses)}")  # 12 (2 + 9 + 1)

// LeetCode 198: House Robber
// Time: O(n), Space: O(1)
#include <vector>
#include <algorithm>

class HouseRobber {
public:
    static int rob(std::vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return nums[0];

        int prev2 = nums[0];
        int prev1 = std::max(nums[0], nums[1]);

        for (int i = 2; i < nums.size(); i++) {
            int curr = std::max(nums[i] + prev2, prev1);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
};

// LeetCode 198: House Robber
// Time: O(n), Space: O(1)

class HouseRobber {
    public static int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        int prev2 = nums[0];
        int prev1 = Math.max(nums[0], nums[1]);

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

5. 2D DP: Longest Common Subsequence

Given two strings, find the length of their longest common subsequence (characters in order but not necessarily contiguous). This is the gateway 2D DP problem — state is defined by two pointers into the two strings. If characters match, both advance; otherwise, try advancing each pointer separately and take the maximum. State: $dp[i][j]$ = LCS length of $text1[0..i-1]$ and $text2[0..j-1]$. Transition: if $text1[i-1] = text2[j-1]$, then $dp[i][j] = dp[i-1][j-1] + 1$; else $dp[i][j] = \max(dp[i-1][j], dp[i][j-1])$.

This pattern generalizes to Edit Distance (add insert/delete/replace costs), Shortest Common Supersequence, and many string-comparison problems.

def longest_common_subsequence(text1, text2):
    """
    LeetCode 1143: Longest Common Subsequence
    Time: O(m*n), Space: O(m*n)
    """
    m, n = len(text1), len(text2)

    # dp[i][j] = LCS of text1[0:i] and text2[0:j]
    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]

# Example
text1 = "abcde"
text2 = "ace"
print(f"LCS of '{text1}' and '{text2}': {longest_common_subsequence(text1, text2)}")  # 3

// LeetCode 1143: Longest Common Subsequence
// Time: O(m*n), Space: O(m*n)
#include <string>
#include <vector>
#include <algorithm>

class LongestCommonSubsequence {
public:
    static int longestCommonSubsequence(std::string text1, std::string text2) {
        int m = text1.size(), n = text2.size();
        std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

        for (int i = 1; i <= m; i++) {
            for (int 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] = std::max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[m][n];
    }
};

// LeetCode 1143: Longest Common Subsequence
// Time: O(m*n), Space: O(m*n)

class LongestCommonSubsequence {
    public static int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i-1) == text2.charAt(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];
    }
}

6. 2D DP: Coin Change

Given coin denominations and a target amount, find the minimum number of coins to make that amount. This is an unbounded knapsack variant — each coin can be used unlimited times. Build up solutions from amount 0 to target: for each amount $a$, try every coin that fits and take the minimum. State: $dp[a]$ = fewest coins to make amount $a$. Transition: $dp[a] = \min(dp[a-coin] + 1)$ for each $coin \le a$. Unlike 0/1 Knapsack where items are used once, here we iterate over coins in the inner loop because reuse is allowed.

def coin_change(coins, amount):
    """
    LeetCode 322: Coin Change
    Minimum coins to make amount
    Time: O(amount * len(coins)), Space: O(amount)
    """
    # dp[i] = minimum coins to make amount i
    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

def coin_change_ways(coins, amount):
    """
    LeetCode 518: Coin Change 2
    Number of ways to make amount
    """
    dp = [0] * (amount + 1)
    dp[0] = 1

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]

# Examples
coins = [1, 2, 5]
amount = 11
print(f"Coins: {coins}, Amount: {amount}")
print(f"Min coins: {coin_change(coins, amount)}")  # 3 (5+5+1)
print(f"Number of ways: {coin_change_ways(coins, amount)}")

// LeetCode 322: Coin Change (min coins)
// LeetCode 518: Coin Change 2 (number of ways)
#include <vector>
#include <algorithm>
#include <limits>

class CoinChange {
public:
    // Min coins to make amount
    static int coinChange(std::vector<int>& coins, int amount) {
        std::vector<int> dp(amount + 1, std::numeric_limits<int>::max());
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i && dp[i - coin] != std::numeric_limits<int>::max())
                    dp[i] = std::min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] == std::numeric_limits<int>::max() ? -1 : dp[amount];
    }

    // Number of ways to make amount
    static int coinChangeWays(std::vector<int>& coins, int amount) {
        std::vector<int> dp(amount + 1, 0);
        dp[0] = 1;

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++)
                dp[i] += dp[i - coin];
        }
        return dp[amount];
    }
};

// LeetCode 322: Coin Change (min coins)
// LeetCode 518: Coin Change 2 (number of ways)
import java.util.*;

class CoinChange {
    // Min coins to make amount
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i && dp[i - coin] != Integer.MAX_VALUE)
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }

    // Number of ways to make amount
    public static int coinChangeWays(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++)
                dp[i] += dp[i - coin];
        }
        return dp[amount];
    }
}

7. Knapsack Problem

The 0/1 Knapsack is the quintessential DP problem: given $n$ items each with a weight and value, maximize total value without exceeding a weight capacity. "0/1" means each item is either taken or left — no fractions. State: $dp[w]$ = max value achievable with capacity $w$. The key insight is traversing the capacity backwards in the 1D optimization — this prevents using the same item twice. The Unbounded Knapsack variant (items reusable) traverses forwards instead.

Knapsack Family

Many problems reduce to knapsack: Subset Sum (can you make target?), Partition Equal Subset Sum (split into two equal halves), Coin Change (unbounded knapsack with min count), and Target Sum (assign +/- signs). The 0/1 vs unbounded distinction determines inner loop direction.

def knapsack_01(weights, values, capacity):
    """
    0/1 Knapsack Problem
    Each item can be taken at most once
    Time: O(n * capacity), Space: O(capacity)
    """
    n = len(weights)

    # Space-optimized: 1D array
    dp = [0] * (capacity + 1)

    for i in range(n):
        # Traverse backwards to avoid using same item twice
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[capacity]

def knapsack_unbounded(weights, values, capacity):
    """
    Unbounded Knapsack
    Each item can be taken multiple times
    """
    dp = [0] * (capacity + 1)

    for w in range(1, capacity + 1):
        for i in range(len(weights)):
            if weights[i] <= w:
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[capacity]

# Example
weights = [1, 2, 3, 4]
values = [10, 20, 30, 40]
capacity = 5

print(f"Weights: {weights}")
print(f"Values: {values}")
print(f"Capacity: {capacity}")
print(f"0/1 Knapsack: {knapsack_01(weights, values, capacity)}")  # 50
print(f"Unbounded Knapsack: {knapsack_unbounded(weights, values, capacity)}")  # 50

// Knapsack Problems
// 0/1 Knapsack and Unbounded Knapsack
#include <vector>
#include <algorithm>

class Knapsack {
public:
    // 0/1 Knapsack - each item at most once
    static int knapsack01(std::vector<int>& weights, std::vector<int>& values, int capacity) {
        int n = weights.size();
        std::vector<int> dp(capacity + 1, 0);

        for (int i = 0; i < n; i++) {
            // Traverse backwards to avoid using same item twice
            for (int w = capacity; w >= weights[i]; w--)
                dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);
        }
        return dp[capacity];
    }

    // Unbounded Knapsack - unlimited of each item
    static int knapsackUnbounded(std::vector<int>& weights, std::vector<int>& values, int capacity) {
        std::vector<int> dp(capacity + 1, 0);

        for (int w = 1; w <= capacity; w++) {
            for (int i = 0; i < weights.size(); i++) {
                if (weights[i] <= w)
                    dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
        return dp[capacity];
    }
};

// Knapsack Problems
// 0/1 Knapsack and Unbounded Knapsack

class Knapsack {
    // 0/1 Knapsack - each item at most once
    public static int knapsack01(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[] dp = new int[capacity + 1];

        for (int i = 0; i < n; i++) {
            // Traverse backwards to avoid using same item twice
            for (int w = capacity; w >= weights[i]; w--)
                dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
        return dp[capacity];
    }

    // Unbounded Knapsack - unlimited of each item
    public static int knapsackUnbounded(int[] weights, int[] values, int capacity) {
        int[] dp = new int[capacity + 1];

        for (int w = 1; w <= capacity; w++) {
            for (int i = 0; i < weights.length; i++) {
                if (weights[i] <= w)
                    dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
        return dp[capacity];
    }
}

8. Pattern Comparison Table

Each problem above states its recurrence in prose. This table collects them side by side so the shared shape — and the differences that matter — are visible at a glance.

Problem	State Definition	Recurrence	Time	Space
Climbing Stairs	`dp[i]` = ways to reach step `i`	`dp[i] = dp[i-1] + dp[i-2]`	O(n)	O(1)
House Robber	`dp[i]` = max loot from houses `0..i`	`dp[i] = max(dp[i-1], dp[i-2] + nums[i])`	O(n)	O(1)
Kadane's Algorithm	`dp[i]` = max subarray sum ending at index `i`	`dp[i] = max(nums[i], dp[i-1] + nums[i])`	O(n)	O(1)
Min-Cost Climbing Stairs	`dp[i]` = min cost to reach step `i`	`dp[i] = cost[i] + min(dp[i-1], dp[i-2])`	O(n)	O(1)
Longest Common Subsequence	`dp[i][j]` = LCS length of `text1[0..i-1]` and `text2[0..j-1]`	`dp[i][j] = dp[i-1][j-1] + 1` if characters match, else `max(dp[i-1][j], dp[i][j-1])`	O(m·n)	O(m·n)
Coin Change	`dp[a]` = fewest coins to make amount `a`	`dp[a] = min(dp[a-coin] + 1)` over each coin ≤ `a`	O(amount·coins)	O(amount)
0/1 Knapsack	`dp[w]` = max value achievable with capacity `w`	`dp[w] = max(dp[w], dp[w-weight[i]] + value[i])`, capacity traversed backwards per item	O(n·capacity)	O(capacity)

9. Exercises and Mastery

Easy

Min Cost Climbing Stairs (LeetCode 746): each step has a cost, and you may start at index 0 or index 1. Find the minimum total cost to reach the top. Adapt the Climbing Stairs recurrence so each transition also adds cost[i], then verify your base cases still make sense with the new starting rule.

Medium

Longest Palindromic Subsequence: run the Longest Common Subsequence algorithm between a string and its own reverse. Explain why the result equals the longest palindromic subsequence, and identify one situation (repeated characters) where you should double-check that the equivalence still holds.

Hard

The 0/1 Knapsack section above already states the full recurrence: state dp[w], transition dp[w] = max(dp[w], dp[w-weight[i]] + value[i]), and the backwards-traversal justification. Trace it by hand instead of re-deriving it: with weights = [1, 2, 3, 4], values = [10, 20, 30, 40], capacity = 5, recompute the dp array for w = 0..5 after each item is processed, and confirm the final answer is 50.

Mastery challenge: A scheduling service has a list of tasks, each with a duration and a value, and a fixed daily time budget. No task can run twice. Decide which pattern in this lesson the problem reduces to, define dp[] precisely, derive the recurrence, and state the time and space complexity — before writing any code.

Review rhythm: tomorrow, rederive all five recurrences from memory without looking at the code; next week, implement Climbing Stairs, House Robber, and Coin Change from scratch in one sitting; several weeks later, solve Min Cost Climbing Stairs and Longest Palindromic Subsequence without hints. Finally, teach someone else why 0/1 Knapsack traverses capacity backwards while Coin Change and Unbounded Knapsack traverse it forwards.

10. Summary Cheat Sheet

1D DP uses a single index; 2D DP uses two indices (two strings, or item × capacity).
Climbing Stairs and House Robber both reduce to a rolling recurrence over dp[i-1] and dp[i-2] — O(n) time, O(1) space once space-optimized.
LCS is the gateway 2D DP problem: match and advance both pointers, or skip one and take the max.
Coin Change is an unbounded knapsack in disguise — coins are reusable, so the coin loop stays inside the amount loop.
0/1 Knapsack traverses capacity backwards to enforce "use each item at most once"; Unbounded Knapsack traverses forwards to allow reuse.
Subset Sum, Partition Equal Subset Sum, and Target Sum are all knapsack in disguise — the pattern, not the story, defines the recurrence.