Back to Algorithms & Data Structures
Algorithms & Data Structures·Algorithms··

Dynamic Programming

Define states and transitions for overlapping subproblems, from knapsacks to stock and subsequence families.

Algorithm Summary

Recursion and dynamic programming both break a problem into smaller subproblems. Dynamic programming stores their answers so overlapping work is not repeated.

Use a five-step process:

  1. Define the DP state and the meaning of every index.
  2. Derive the recurrence.
  3. Decide the base cases and initialization.
  4. Choose a traversal order that makes dependencies available.
  5. Simulate a small example by hand before coding.

When an implementation fails, print the DP table. If it matches the hand simulation, revisit the state, transition, initialization, or traversal order. If it differs, the bug is in the implementation details.

0/1 knapsack

There are N items, item i has weight weight[i] and value value[i], and every item may be used at most once. For a bag of capacity W, define dp[i][j] as the maximum value achievable with the first i items and capacity j.

Plain text
dp[i][j] = max(
    dp[i - 1][j],
    dp[i - 1][j - weight[i]] + value[i]
)

The transition compares skipping the item with taking it. A two-dimensional implementation is:

Java
int[][] dp = new int[N + 1][W + 1];
for (int i = 1; i <= N; i++) {
    int weight = weights[i - 1];
    int value = values[i - 1];
    for (int capacity = 1; capacity <= W; capacity++) {
        dp[i][capacity] = dp[i - 1][capacity];
        if (capacity >= weight) {
            dp[i][capacity] = Math.max(
                dp[i][capacity],
                dp[i - 1][capacity - weight] + value
            );
        }
    }
}

Because each row depends only on the previous row, compress it to dp[capacity]. Traverse capacity from high to low so an item is not reused in the same iteration.

Java
for (int i = 0; i < N; i++) {
    for (int capacity = W; capacity >= weights[i]; capacity--) {
        dp[capacity] = Math.max(dp[capacity], dp[capacity - weights[i]] + values[i]);
    }
}

0/1 knapsack problem notes

  • Partition Equal Subset Sum — LC 416: ask whether a subset can exactly fill capacity sum / 2.
  • Last Stone Weight II — LC 1049: fill a bag of capacity sum / 2 as much as possible, then compare the two partitions.
  • Target Sum — LC 494: convert signs into a subset-count problem. If positive - negative = target and positive + negative = sum, then positive = (target + sum) / 2.
  • Ones and Zeroes — LC 474: a two-dimensional 0/1 knapsack where zeros and ones are separate capacities and the value is the subset size.

Unbounded knapsack

Every item may be reused. The one-dimensional transition looks like 0/1 knapsack, but capacity must run from low to high so the current item can contribute more than once.

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

Traversal order determines what is counted:

  • For combinations, iterate items outside and capacity inside.
  • For permutations, iterate capacity outside and items inside.

Unbounded knapsack problem notes

  • Coin Change II — LC 518: count combinations that make the target. Use dp[amount] += dp[amount - coin] with coins in the outer loop.
  • Combination Sum IV — LC 377: count ordered sequences. Use the same recurrence with target amounts in the outer loop.
  • Climbing Stairs, generalized: steps 1...m are reusable items and the stair count is the target; order matters.
  • Coin Change — LC 322: minimize the number of coins with dp[amount] = min(dp[amount], dp[amount - coin] + 1).
  • Perfect Squares — LC 279: perfect squares are reusable items; minimize how many are needed to fill n.
  • Word Break — LC 139: dp[i] is true when the prefix ending at i can be formed from dictionary words.

House robber family

For a linear street, define dp[i] as the maximum amount available from houses 0...i.

Plain text
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
  • House Robber — LC 198: choose between skipping the current house and taking it after the best result two positions back.
  • House Robber II — LC 213: houses form a circle, so solve two linear ranges: exclude the first house or exclude the last house, then take the larger result.

Stock-trading states

All stock problems assume a held stock must be sold before another is bought. Define states by whether a stock is held and, when necessary, how many transactions have been completed.

  • Best Time to Buy and Sell Stock — LC 121: one transaction. The held state is max(previously held, -price).
  • Best Time to Buy and Sell Stock II — LC 122: unlimited transactions. A new held state may come from yesterday's unheld profit minus today's price.
  • Best Time to Buy and Sell Stock III — LC 123: use five states: no action, first hold, first sale, second hold, second sale.
  • Best Time to Buy and Sell Stock IV — LC 188: generalize to 2k + 1 states; odd indices hold stock and even indices do not.
  • Best Time to Buy and Sell Stock with Cooldown — LC 309: distinguish held, resting, sold today, and cooldown states.
  • Best Time to Buy and Sell Stock with Transaction Fee — LC 714: use the unlimited-transactions recurrence and subtract the fee when selling.

Subsequences

Longest increasing subsequence

Let dp[i] be the longest increasing subsequence ending at nums[i]. Every earlier smaller value can extend into position i.

Java
Arrays.fill(dp, 1);
for (int i = 1; i < nums.length; i++) {
    for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
}

The final answer is the maximum value in dp, not necessarily dp[n - 1].

  • Longest Increasing Subsequence — LC 300: compare every earlier position.
  • Longest Continuous Increasing Subsequence — LC 674: continuity means each state depends only on the immediately previous value.

Common subsequences

For two sequences, let dp[i][j] be the longest common subsequence of their first i and j values.

Plain text
if s1[i - 1] == s2[j - 1]:
    dp[i][j] = dp[i - 1][j - 1] + 1
else:
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
  • Maximum Length of Repeated Subarray — LC 718: require continuity, so matching values extend only dp[i - 1][j - 1].
  • Longest Common Subsequence — LC 1143: order matters but continuity does not.
  • Uncrossed Lines — LC 1035: equivalent to longest common subsequence.

Edit-distance family

  • Edit Distance — LC 72: when characters differ, take one plus the minimum of delete from word one, delete from word two, or replace both characters.
  • Distinct Subsequences — LC 115: when characters match, count both using the current source character and skipping it; otherwise only skipping is possible.
  • Delete Operation for Two Strings — LC 583: either use the longest common subsequence or define a direct minimum-deletion DP.
Plain text
if word1[i - 1] == word2[j - 1]:
    dp[i][j] = dp[i - 1][j - 1]
else:
    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1

Palindromes

  • Palindromic Substrings — LC 647: use a two-dimensional state indicating whether a substring is a palindrome, or expand around every center.
  • Longest Palindromic Subsequence — LC 516: matching ends extend the inner subsequence by two; otherwise drop one end and take the larger state.
Back to Algorithms & Data Structures