Category 8

Dynamic Programming

Master the art of breaking complex problems into overlapping subproblems and combining optimal solutions. Learn top-down memoization, bottom-up tabulation, and space-optimized state transitions across 15 essential problems.

15
Problems
3
Difficulty Levels
100%
Complete Solutions
5
Codility Problems
Theory

Dynamic Programming Fundamentals

Dynamic programming solves complex problems by breaking them into overlapping subproblems, caching results, and combining optimal solutions. Two implementation styles exist: top-down (memoization) and bottom-up (tabulation).

1. Core Principles of DP

Overlapping Subproblems: The same subproblem is solved multiple times. Instead of recomputing, cache results in a dictionary (memoization) or array (tabulation).

Optimal Substructure: An optimal solution can be constructed from optimal solutions to its subproblems. This allows recurrence relations.

State Definition: Clearly define what dp[i] or dp[i][j] represents. Common patterns: longest sequence ending at i, minimum cost to reach state i, count of ways to achieve state i.

Recurrence Relation: Express the current state in terms of previous states.

Base Cases: Identify initial conditions that require no computation.

Fill Order: In tabulation, process states in dependency order (usually left-to-right or bottom-up for 2D).

2. Top-Down (Memoization) vs Bottom-Up (Tabulation)

Aspect Top-Down (Memoization) Bottom-Up (Tabulation)
Approach Recursive with caching Iterative DP array
When to use Natural recursive structure, not all states needed All states needed, clear iteration order
Implementation Dictionary + recursion Array + loops
Space O(depth of recursion) + O(states) O(states)
Typical overhead Recursion stack, hash lookups Cleaner, cache-friendly

3. Identifying DP Problems

Keywords that suggest DP:

4. Common DP Patterns

💡
1D DP (Linear): dp[i] depends on dp[i-1], dp[i-2], etc. Examples: Fibonacci, climbing stairs, longest increasing subsequence.
💡
2D DP (Grid/String): dp[i][j] depends on neighbors. Examples: LCS, edit distance, unique paths in grid.
💡
Knapsack: dp[i][w] = max value using first i items with capacity w. Variants: 0/1, unbounded, multidimensional.
💡
Interval/Range DP: dp[i][j] = optimal for subarray/substring from i to j. Build up from small intervals to large.
💡
Space Optimization: If dp[i] only depends on previous row/column, use rolling arrays (two arrays instead of full 2D). Reduces space from O(n*m) to O(m).

5. Space Optimization Techniques

Rolling Array: Keep only the last two rows instead of entire 2D array.

csharp 
// Example: Optimize 2D DP to O(n) space using rolling array
int[] prev = new int[m];
int[] curr = new int[m];
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        curr[j] = Math.Max(prev[j], curr[j-1]);
    }
    prev = curr;
}
Problems

15 Essential DP Problems

1. NumberSolitaire (Codility)
Find the maximum sum achievable in a path from position 0 to n-1, where each step can be 1 to 6 positions forward.
1D DP Codility ★★
01

Problem Statement

You have an array A of size N. Start at position 0. At each step, you can move forward by 1 to 6 positions and add A[next_pos] to your sum. Reach position N-1 with maximum sum.

State Definition

dp[i] = maximum sum achievable when reaching position i.

Recurrence Relation

dp[i] = A[i] + max(dp[i-1], dp[i-2], ..., dp[i-6]) (for all valid previous positions)

Base Case

dp[0] = A[0]

Implementation

csharp 
public int NumberSolitaire(int[] A) {
    int N = A.Length;
    int[] dp = new int[N];
    dp[0] = A[0];

    for (int i = 1; i < N; i++) {
        dp[i] = int.MinValue;
        // Try moves from 1 to 6 steps back
        for (int jump = 1; jump <= 6 && jump <= i; jump++) {
            dp[i] = Math.Max(dp[i], dp[i - jump] + A[i]);
        }
    }

    return dp[N - 1];
}

Trace Example

A = [1, -2, 0, 9, 2, -4, 4]

dp[0]=1, dp[1]=max(1-2)=-1, dp[2]=max(-1+0, 1+0)=1, dp[3]=max(1+9, -1+9, 1+9)=10, dp[4]=max(1+2)=3, dp[5]=max(1-4)=-3, dp[6]=max(10+4)=14

Complexity

Time: O(N × 6) = O(N) | Space: O(N)

Edge Cases

  • N = 1: Return A[0]
  • Negative values in array: DP still finds maximum reachable
  • Large sums: Use long if needed
2. MinAbsSum (Codility)
Find the minimum absolute value of any sum of elements from array A (can use all, some, or none).
Subset Sum Codility ★★★
02

Problem Statement

Given array A of integers (can be negative). Find subset such that the absolute value of the sum is minimized. Return this minimum absolute value.

Key Insight

This is a variant of partition problem. For total sum S, partition array into two subsets P and N such that sum(P) - sum(N) = S - 2*sum(N). To minimize |result|, we want sum(P) and sum(N) as close as possible.

State Definition

dp[i] = true if sum i is achievable. Track all reachable sums, find closest to 0.

Implementation

csharp 
public int MinAbsSum(int[] A) {
    int sumPos = 0;
    for (int i = 0; i < A.Length; i++) {
        sumPos += Math.Abs(A[i]);
    }

    // DP: track which sums are achievable
    bool[] dp = new bool[sumPos + 1];
    dp[0] = true;

    for (int i = 0; i < A.Length; i++) {
        int val = Math.Abs(A[i]);
        // Traverse backwards to avoid using same element twice
        for (int s = sumPos; s >= val; s--) {
            if (dp[s - val]) dp[s] = true;
        }
    }

    // Find closest achievable sum to 0
    int minAbs = sumPos;
    for (int s = 0; s <= sumPos; s++) {
        if (dp[s]) {
            minAbs = Math.Min(minAbs, Math.Min(s, sumPos - 2 * s));
        }
    }

    return minAbs;
}

Complexity

Time: O(N × SUM) where SUM is sum of absolute values | Space: O(SUM)

Edge Cases

  • All positive or all negative: minimum is single smallest element
  • Mixed signs: partition optimally
  • Large absolute values: SUM can be large; time may be high
3. Climbing Stairs (LC 70)
Count ways to climb N stairs when each step covers 1 or 2 stairs.
Fibonacci LeetCode ★
03

Problem Statement

You are climbing a staircase with N stairs. Each time you can climb 1 or 2 stairs. How many distinct ways can you climb to the top?

State Definition

dp[i] = number of ways to reach stair i.

Recurrence Relation

dp[i] = dp[i-1] + dp[i-2] (either step from i-1 or i-2)

Base Cases

dp[0] = 1 (one way to stay at start), dp[1] = 1 (one way to reach first stair)

Implementation (Space-Optimized)

csharp 
public int ClimbStairs(int n) {
    if (n <= 1) return 1;

    int prev2 = 1; // dp[0]
    int prev1 = 1; // dp[1]

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

    return prev1;
}

Trace Example

n = 5

dp[0]=1, dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=5, dp[5]=8 → Answer: 8

Complexity

Time: O(N) | Space: O(1) optimized, O(N) with full array

Edge Cases

  • n = 1: return 1
  • n = 2: return 2
  • Large n: may overflow int (use long)
4. House Robber (LC 198)
Maximize money robbed from houses in a line, where adjacent houses cannot be robbed.
1D DP LeetCode ★★
04

Problem Statement

Array of house values. Rob houses to maximize total, but cannot rob two adjacent houses. Return maximum money.

State Definition

dp[i] = maximum money robbed up to house i.

Recurrence Relation

dp[i] = max(dp[i-1], dp[i-2] + A[i]) (skip house or rob it)

Implementation

csharp 
public int Rob(int[] nums) {
    if (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(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }

    return prev1;
}

Trace Example

nums = [1, 3, 1, 3, 100]

dp[0]=1, dp[1]=3, dp[2]=max(3,1+1)=3, dp[3]=max(3,3+3)=6, dp[4]=max(6,3+100)=103 → Answer: 103

Complexity

Time: O(N) | Space: O(1)

5. Coin Change (LC 322)
Find minimum number of coins needed to make a target amount.
Unbounded Knapsack LeetCode ★★
05

Problem Statement

Array of coin denominations. Find minimum number of coins to make amount. Unlimited supply of each coin. Return -1 if impossible.

State Definition

dp[i] = minimum coins needed to make amount i.

Recurrence Relation

dp[i] = 1 + min(dp[i - coin]) for all coins where coin <= i

Base Case

dp[0] = 0 (zero coins for zero amount)

Implementation

csharp 
public int CoinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    for (int i = 1; i <= amount; i++) {
        dp[i] = int.MaxValue;
    }

    for (int i = 1; i <= amount; i++) {
        foreach (int coin in coins) {
            if (coin <= i && dp[i - coin] != int.MaxValue) {
                dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] == int.MaxValue ? -1 : dp[amount];
}

Trace Example

coins = [1, 2, 5], amount = 5

dp[0]=0, dp[1]=1, dp[2]=1, dp[3]=2, dp[4]=2, dp[5]=1 → Answer: 1 (one coin of value 5)

Complexity

Time: O(amount × |coins|) | Space: O(amount)

Edge Cases

  • amount = 0: return 0
  • Impossible to make amount: return -1
  • Single coin: can make only multiples of that coin
6. Longest Increasing Subsequence (LC 300)
Find length of longest strictly increasing subsequence. Includes O(n²) and O(n log n) solutions.
1D DP / Binary Search LeetCode ★★
06

Problem Statement

Array of integers. Find length of longest strictly increasing subsequence (not necessarily contiguous).

State Definition (O(n²) DP)

dp[i] = length of LIS ending at index i.

Recurrence

dp[i] = 1 + max(dp[j]) for all j < i where A[j] < A[i]

O(n²) Implementation

csharp 
public int LengthOfLIS_DP(int[] nums) {
    int[] dp = new int[nums.Length];
    for (int i = 0; i < nums.Length; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.Max(dp[i], dp[j] + 1);
            }
        }
    }
    int maxLen = 0;
    foreach (int len in dp) {
        maxLen = Math.Max(maxLen, len);
    }
    return maxLen;
}

O(n log n) Implementation (Binary Search)

csharp 
public int LengthOfLIS(int[] nums) {
    if (nums.Length == 0) return 0;

    List<int> tails = new List<int>();
    foreach (int num in nums) {
        int pos = tails.BinarySearch(num);
        if (pos < 0) pos = ~pos;

        if (pos == tails.Count) {
            tails.Add(num);
        } else {
            tails[pos] = num;
        }
    }
    return tails.Count;
}

Trace Example

nums = [10, 9, 2, 5, 3, 7, 101, 18]

O(n²): dp = [1,1,1,2,2,3,4,4] → max = 4 ([2,3,7,101] or [2,5,7,101])

O(n log n): tails evolves as [10], [9], [2], [2,5], [2,3], [2,3,7], [2,3,7,101], [2,3,7,18]

Complexity

O(n²) Time: O(N²) | Space: O(N)

O(n log n) Time: O(N log N) | Space: O(N)

7. Word Break (LC 139)
Determine if a string can be segmented using words from a dictionary.
String DP + HashSet LeetCode ★★
07

Problem Statement

String s and word dictionary. Check if s can be segmented as concatenation of dictionary words (each word used at most once per position).

State Definition

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

Recurrence

dp[i] = true if there exists j < i where dp[j] is true and s[j..i-1] is in dictionary

Implementation

csharp 
public bool WordBreak(string s, IList<string> wordDict) {
    var dict = new HashSet<string>(wordDict);
    bool[] dp = new bool[s.Length + 1];
    dp[0] = true;

    for (int i = 1; i <= s.Length; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.Contains(s.Substring(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.Length];
}

Trace Example

s = "applepenapple", dict = ["apple", "pen"]

dp[0]=T, dp[5]=T (apple), dp[8]=T (apple+pen), dp[13]=T (apple+pen+apple) → true

Complexity

Time: O(N² × M) where N = len(s), M = avg word length (substring creation) | Space: O(N)

Optimization Tip

If word lengths are bounded, prune j iterations: for (int j = Math.Max(0, i - maxWordLen); ...)

8. Unique Paths (LC 62)
Count distinct paths in m×n grid from top-left to bottom-right (move right or down only).
2D Grid DP LeetCode ★★
08

Problem Statement

m×n grid. Start at (0,0), end at (m-1,n-1). Each move is either right or down. Count distinct paths.

State Definition

dp[i][j] = number of ways to reach cell (i,j).

Recurrence

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

Base Cases

dp[0][0] = 1, first row and column all 1 (only one way)

Implementation

csharp 
public int UniquePaths(int m, int n) {
    int[][] dp = new int[m][];
    for (int i = 0; i < m; i++) {
        dp[i] = new int[n];
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 1;
            } else {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }

    return dp[m - 1][n - 1];
}

Space-Optimized Implementation

csharp 
public int UniquePaths_Optimized(int m, int n) {
    int[] prev = new int[n];
    for (int j = 0; j < n; j++) prev[j] = 1;

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            prev[j] += prev[j - 1];
        }
    }

    return prev[n - 1];
}

Complexity

Time: O(m × n) | Space: O(m × n) or O(n) optimized

Mathematical Note

This is equivalent to choosing m-1 down moves from m+n-2 total moves: C(m+n-2, m-1)

9. Minimum Path Sum (LC 64)
Find minimum sum path from top-left to bottom-right in grid (move right or down only).
2D Grid DP LeetCode ★★
09

Problem Statement

m×n grid with integers. Find path from (0,0) to (m-1,n-1) with minimum sum. Move right or down only.

State Definition

dp[i][j] = minimum sum to reach cell (i,j).

Recurrence

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Implementation

csharp 
public int MinPathSum(int[][] grid) {
    int m = grid.Length, n = grid[0].Length;
    int[][] dp = new int[m][];
    for (int i = 0; i < m; i++) {
        dp[i] = new int[n];
    }

    dp[0][0] = grid[0][0];

    // Fill first row
    for (int j = 1; j < n; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }

    // Fill first column
    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }

    // Fill remaining cells
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = grid[i][j] + Math.Min(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[m - 1][n - 1];
}

Trace Example

grid = [[1,3,1], [1,5,1], [4,2,1]]

dp[0]=[1,4,5], dp[1]=[2,7,6], dp[2]=[6,8,7] → Answer: 7

Complexity

Time: O(m × n) | Space: O(m × n)

In-Place Optimization

Can modify grid directly instead of using separate dp array (if allowed).

10. Edit Distance (LC 72)
Find minimum edits (insert, delete, replace) to transform one string to another.
2D String DP LeetCode ★★★
10

Problem Statement

Two strings word1 and word2. Find minimum edits (insert, delete, replace char) to convert word1 to word2. Each operation counts as 1 edit.

State Definition

dp[i][j] = minimum edits to convert word1[0..i-1] to word2[0..j-1].

Recurrence

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], dp[i][j-1], dp[i-1][j-1]) (delete, insert, replace)

Base Cases

dp[0][j] = j (insert j chars), dp[i][0] = i (delete i chars)

Implementation

csharp 
public int MinDistance(string word1, string word2) {
    int m = word1.Length, n = word2.Length;
    int[][] dp = new int[m + 1][];
    for (int i = 0; i <= m; i++) {
        dp[i] = new int[n + 1];
    }

    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    for (int i = 1; i <= m; i++) {
        for (int 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 + Math.Min(
                    Math.Min(dp[i - 1][j], dp[i][j - 1]),
                    dp[i - 1][j - 1]);
            }
        }
    }

    return dp[m][n];
}

Trace Example

word1 = "horse", word2 = "ros"

Build 6×4 matrix, final dp[5][3] = 3 (delete h, delete e, replace p→s)

Complexity

Time: O(m × n) | Space: O(m × n), optimizable to O(min(m,n))

11. Longest Common Subsequence (LC 1143)
Find length of longest subsequence common to both strings.
2D String DP LeetCode ★★
11

Problem Statement

Two strings text1 and text2. Find length of longest subsequence appearing in both (not necessarily contiguous).

State Definition

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

Recurrence

If text1[i-1] == text2[j-1]: dp[i][j] = 1 + dp[i-1][j-1]

Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Base Cases

dp[0][j] = 0, dp[i][0] = 0

Implementation

csharp 
public int LongestCommonSubsequence(string text1, string text2) {
    int m = text1.Length, n = text2.Length;
    int[][] dp = new int[m + 1][];
    for (int i = 0; i <= m; i++) {
        dp[i] = new int[n + 1];
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.Max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
}

Trace Example

text1 = "ace", text2 = "abe"

dp[1][1]='a', dp[2][2]='a', dp[3][3]='ae' → Answer: 2

Complexity

Time: O(m × n) | Space: O(m × n)

Reconstruction

To find the actual LCS string, backtrack from dp[m][n] following the path that produced max values.

12. 0/1 Knapsack (Classic)
Maximize value with weight constraint, using each item at most once.
0/1 Knapsack Classic ★★
12

Problem Statement

N items with weights and values. Knapsack capacity W. Maximize total value without exceeding capacity. Each item can be selected 0 or 1 time.

State Definition

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

Recurrence

If weight[i-1] > w: dp[i][w] = dp[i-1][w] (cannot fit, skip)

Else: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i-1]] + value[i-1])

Implementation

csharp 
public int Knapsack01(int[] weights, int[] values, int W) {
    int N = weights.Length;
    int[][] dp = new int[N + 1][];
    for (int i = 0; i <= N; i++) {
        dp[i] = new int[W + 1];
    }

    for (int i = 1; i <= N; i++) {
        for (int w = 0; w <= W; w++) {
            if (weights[i - 1] > w) {
                dp[i][w] = dp[i - 1][w];
            } else {
                dp[i][w] = Math.Max(
                    dp[i - 1][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            }
        }
    }

    return dp[N][W];
}

Space-Optimized (1D)

csharp 
public int Knapsack01_Optimized(int[] weights, int[] values, int W) {
    int[] dp = new int[W + 1];

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

    return dp[W];
}

Trace Example

weights = [2, 3, 4], values = [3, 4, 5], W = 5

Optimal: items 0,1 with total weight 5, value 7

Complexity

Time: O(N × W) | Space: O(N × W) or O(W) optimized

13. Partition Equal Subset Sum (LC 416)
Check if array can be partitioned into two subsets with equal sum.
Subset Sum DP LeetCode ★★
13

Problem Statement

Array of integers. Determine if it can be partitioned into two subsets with equal sum.

Key Insight

If total sum is odd, impossible. If even, check if we can achieve sum/2 using subset sum DP (same as MinAbsSum variant).

State Definition

dp[i] = true if sum i is achievable using some subset.

Implementation

csharp 
public bool CanPartition(int[] nums) {
    int sum = 0;
    foreach (int num in nums) sum += num;

    if (sum % 2 != 0) return false;

    int target = sum / 2;
    bool[] dp = new bool[target + 1];
    dp[0] = true;

    foreach (int num in nums) {
        // Traverse backwards to use each element once
        for (int i = target; i >= num; i--) {
            dp[i] = dp[i] || dp[i - num];
        }
    }

    return dp[target];
}

Trace Example

nums = [1, 5, 11, 5]

Total = 22, target = 11. Build dp array, dp[11] becomes true (via 5+5+1 or 11) → true

Complexity

Time: O(N × SUM/2) | Space: O(SUM/2)

Early Exit Optimization

If dp[target] becomes true, can break early from outer loop.

14. Longest Palindromic Substring (LC 5)
Find longest substring that reads the same forwards and backwards.
String DP / Expand LeetCode ★★
14

Problem Statement

String s. Find longest contiguous palindromic substring. Return the substring itself.

DP Solution

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

If s[i] == s[j] and (j-i <= 1 or dp[i+1][j-1]): dp[i][j] = true

DP Implementation

csharp 
public string LongestPalindrome_DP(string s) {
    int n = s.Length;
    if (n < 2) return s;

    bool[][] dp = new bool[n][];
    for (int i = 0; i < n; i++) {
        dp[i] = new bool[n];
        dp[i][i] = true;
    }

    int start = 0, maxLen = 1;

    // Check length 2
    for (int i = 0; i < n - 1; i++) {
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = true;
            start = i; maxLen = 2;
        }
    }

    // Check length 3+
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                start = i; maxLen = len;
            }
        }
    }

    return s.Substring(start, maxLen);
}

Expand-Around-Center Solution (More Efficient)

csharp 
public string LongestPalindrome(string s) {
    if (s.Length < 2) return s;

    int start = 0, maxLen = 1;

    for (int i = 0; i < s.Length; i++) {
        // Odd-length palindromes (center = single char)
        var (l1, r1) = ExpandAroundCenter(s, i, i);
        if (r1 - l1 + 1 > maxLen) {
            start = l1;
            maxLen = r1 - l1 + 1;
        }

        // Even-length palindromes (center = between chars)
        var (l2, r2) = ExpandAroundCenter(s, i, i + 1);
        if (r2 - l2 + 1 > maxLen) {
            start = l2;
            maxLen = r2 - l2 + 1;
        }
    }

    return s.Substring(start, maxLen);
}

private (int, int) ExpandAroundCenter(string s, int left, int right) {
    while (left >= 0 && right < s.Length && s[left] == s[right]) {
        left--;
        right++;
    }
    return (left + 1, right - 1);
}

Complexity

DP Time: O(N²) | Space: O(N²)

Expand Time: O(N²) | Space: O(1)

15. Best Time Buy Sell Stock with Cooldown (LC 309)
Maximize profit with buy/sell operations and 1-day cooldown after each sale.
State Machine DP LeetCode ★★
15

Problem Statement

Array of daily stock prices. Buy and sell to maximize profit. Constraint: after selling on day i, cannot buy on day i+1 (cooldown). Unlimited transactions.

State Definition (State Machine)

hold[i] = max profit at day i if holding stock

sold[i] = max profit at day i after selling (just sold)

rest[i] = max profit at day i if resting (cooldown or not holding)

Recurrence

hold[i] = max(hold[i-1], rest[i-1] - prices[i]) (keep holding or buy)

sold[i] = hold[i-1] + prices[i] (sell today)

rest[i] = max(rest[i-1], sold[i-1]) (cooldown or nothing)

Implementation

csharp 
public int MaxProfit(int[] prices) {
    if (prices.Length <= 1) return 0;

    int hold = -prices[0]; // Buy on day 0
    int sold = 0;        // Haven't sold yet
    int rest = 0;        // No stock, no cooldown

    for (int i = 1; i < prices.Length; i++) {
        int newHold = Math.Max(hold, rest - prices[i]);
        int newSold = hold + prices[i];
        int newRest = Math.Max(rest, sold);

        hold = newHold;
        sold = newSold;
        rest = newRest;
    }

    return Math.Max(sold, rest);
}

Trace Example

prices = [3, 1, 4]

Day 0: hold=-3, sold=0, rest=0

Day 1: hold=max(-3, 0-1)=-1, sold=max(-3+1)=-2, rest=max(0, 0)=0

Day 2: hold=max(-1, 0-4)=-1, sold=max(-1+4)=3, rest=max(0, -2)=0

Answer: max(3, 0) = 3 (buy at 1, sell at 4)

Complexity

Time: O(N) | Space: O(1)

Generalization

This state-machine pattern applies to all stock problems: vary states and transitions.