Topic 12: 1D DP

Key-Intuition: Many dynamic programming problems can be reduced to 1D subproblems involving optimal substructure and overlapping subproblems.

Canonical Question Types #

Linear State Transitions (Fibonacci-like) #

Progression by fixed window of previous states
Problems:

Problems #

Climbing Stairs (70)

Both topdown recursive and bottom up iterative are easy to write, we notice that we can use rolling variables here because there only is a need to keep track of a single historical value.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
    # bottom up iterative 2-var rolling approach
    class Solution:
        def climbStairs(self, n: int) -> int:
            if n <= 2:
                return n

            prev, curr = 1, 2
            for _ in range(3, n+1):
                prev, curr = curr, prev + curr

            return curr

    # top down recursive using builtin cache decorator
    from functools import cache

    class Solution:
        @cache
        def climbStairs(self, n: int) -> int:
            if n <= 2:
                return n

            return self.climbStairs(n - 1) + self.climbStairs(n - 2)

Min Cost Climbing Stairs (746)

Same as previous, now with a cost applied remember the cost is for reaching that step so reach this step == paid the cost of jumping from previous steps; it’s NOT “cost of landing on this step”. You do not need to land on the last step; you need the minimum cost of getting past the last step, so from either the last or second last step.

We realise that we only need one historical state, so a 2-var rolling approach works well for the iterative implementation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
    # bottom up recursive:
    class Solution:
        def minCostClimbingStairs(self, cost: List[int]) -> int:
            if len(cost) == 0:
                return 0
            if len(cost) == 1:
                return cost[0]

            prev, curr = cost[0], cost[1]
            for i in range(2, len(cost)):
                prev, curr = curr, min(prev, curr) + cost[i]

            return min(prev, curr)

    # top down recursive approach:
    from functools import cache
    class Solution:
        def minCostClimbingStairs(self, cost: List[int]) -> int:
            @cache
            def min_cost(i):
                if i < 2: return cost[i]
                return cost[i] + min(min_cost(i-1), min_cost(i-2))
            n = len(cost)

            return min(min_cost(n-1), min_cost(n-2))

Fibonacci Number (509)

Straight up classic.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    class Solution:
        def fib(self, n: int) -> int:
            if n == 0:
                return 0
            if n == 1:
                return 1

            prev, curr = 0, 1
            for _ in range(2, n + 1):
                prev, curr = curr, prev + curr

            return curr

Non-Adjacent Selection (House Robber type) #

Select a subset of elements under adjacency constraints (max sum, choose or skip)

Problems #

House Robber (198)

It’s a max sum and for each element, we either choose it or we skip it. Just need to build up our answer from small to big. We naturally realise that we only need to keep track of 2 states, hence the rolling variables are only 2.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
    # iterative bottom up 2-rolling variables approach.
    class Solution:
        def rob(self, nums: List[int]) -> int:
            if not nums:
                return 0

            if len(nums) == 1:
                return nums[0]


            prev, curr = nums[0], max(nums[1], nums[0])
            for i in range(2, len(nums)):
                this = nums[i]
                prev, curr = curr, max(
                    nums[i] + prev,  # choose this house to rob
                    curr # don't choose this house to rob
                    )

            return curr

    # top down recursive solution
    from functools import cache
    class Solution:
        def rob(self, nums: List[int]) -> int:
            n = len(nums)
            @cache
            def dp(i):
                if i >= n: return 0
                return max(nums[i] + dp(i+2), dp(i+1))
            return dp(0)

House Robber II (213)

The key idea here is that to reduce it to the earlier version, we consider 2 mutually exclusive events (that only exist because of the circular nature). The rest is pretty much the same. Extracting things into a helper function is useful.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
    class Solution:
        def rob(self, nums: List[int]) -> int:
            if not nums:
                return 0
            if len(nums) == 1:
                return nums[0]

            def rob_straight(houses):
                if len(houses) == 0:
                    return 0

                if len(houses) == 1:
                    return houses[0]

                prev, curr = houses[0], max(houses[1], houses[0])
                for i in range(2, len(houses)):
                    this = houses[i]
                    prev, curr = curr, max(
                        houses[i] + prev, # chose this house to rob
                        curr
                    )

                return curr

            # get 1D maxes for the staight-lined version:
            return max(
                rob_straight(nums[1:]), # case 1: we choose last house, forgo first house
                rob_straight(nums[:len(nums) - 1]), # case 2: we choose first house, forgo last house
            )

Maximum Subarray/Product/Range #

Contiguous region optimal (sum or product)

Problems #

Maximum Product Subarray (152)

We just want the max product from a subarray within the array given, it would smell like an inclusion / exclusion kind of problem (either start fresh or continue accumulating) initially so we might be tempted to approach it like a continguous region and 2D DP-table it. However, it’s not always true that we HAVE to pick 2D approaches when we are trying to keep track of contiguous regions, we should consider other properties / characteristics of the problem.

The key insight is that we need to keep track of both min and max at each step because the numbers can be negative and two negatives may give us a positive.

On further observation, we then realise that we do not need explicit two pointers or a 2D DP table because the maximum product subarray ending at index i depends only on max/min products ending at i-1. By tracking just those two variables at each step, you integrate the contribution of all contiguous subarrays ending there and keep the global max in O(n) time and O(1) space.

So a 1D DP table is sufficient:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
    # 1D DP table
    class Solution:
        def maxProduct(self, nums: List[int]) -> int:
            n = len(nums)
            curr_max, curr_min = nums[0], nums[0]
            result = curr_max

            for idx in range(1,len(nums)):
                num = nums[idx]
                # negative multiplication, will swap the min and max values
                if num < 0:
                    curr_min, curr_max = curr_max, curr_min

                # max of (starting fresh, or accumulating)
                curr_max = max(num, curr_max * num)
                curr_min = min(num, curr_min * num)

                result = max(result, curr_max)

            return result

Maximum Subarray (53)

Knapsack/Subset Sum Variants #

Bounded and unbounded choices, partitioning, subset formation

Problems #

Coin Change (322)

Applying the DP framework:

Step Explanation Status/Notes
1. Define Subproblems Number of coins needed to form amount <= target amount dp[i] = min coins needed for amount i
2. Check Overlapping Subproblems dp[i] depends on solutions of dp[i - coin] for each coin Yes, overlapping subproblems exist
3. Identify Choices Per Subproblem Choose any coin from coins that fits into current amount Multiple choices per state
4. Confirm Optimal Substructure Optimal for amount i computed from optimal solutions for smaller amounts Yes, minimum over choices is optimal
5. Compute Solution (Top-Down / Bottom-Up) Bottom-up iterative or top-down memoized recursion both applicable Both implemented correctly
6. (Optional) Construct Actual Solution Can store chosen coins to reconstruct path Not implemented in provided solutions

Step	Explanation	Status/Notes
1. Define Subproblems	Number of coins needed to form amount <= target amount	dp[i] = min coins needed for amount i
2. Check Overlapping Subproblems	dp[i] depends on solutions of dp[i - coin] for each coin	Yes, overlapping subproblems exist
3. Identify Choices Per Subproblem	Choose any coin from coins that fits into current amount	Multiple choices per state
4. Confirm Optimal Substructure	Optimal for amount i computed from optimal solutions for smaller amounts	Yes, minimum over choices is optimal
5. Compute Solution (Top-Down / Bottom-Up)	Bottom-up iterative or top-down memoized recursion both applicable	Both implemented correctly
6. (Optional) Construct Actual Solution	Can store chosen coins to reconstruct path	Not implemented in provided solutions

This question is a DP because we are dealing with arbitrary denominations and with unlimited amounts of each coin. If we had been given a fixed amount, then it would have been a greedy solution instead because we would have to pick the best choice each time (locally optimal) to give the “biggest jump”.

Also note that we’re intentionally doing a 1-idx approach so that dp[i] = min number of ways to make up value = i.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
    # iterative bottom up approach
    class Solution:
        def coinChange(self, coins: List[int], amount: int) -> int:
            # This init of inf avoids negative values by using infinity, making code cleaner.
            dp = [float('inf')] * (amount + 1)
            dp[0] = 0

            for amt in range(1, amount + 1):
                for coin in coins:
                    if coin <= amt:
                        dp[amt] = min(dp[amt], dp[amt - coin] + 1)

            return dp[amount] if dp[amount] != float('inf') else -1

    # recursive topdown approach
    from functools import cache
    class Solution:
        def coinChange(self, coins: List[int], amount: int) -> int:
            @cache
            def helper(amount):
                if amount == 0:
                    return 0

                if amount < 0:
                    return -1

                options = [helper(amount - denom) for denom in coins if
                           amount - denom >= 0 and helper(amount - denom) != -1]

                if not options:
                    return -1
                else:
                    return min(options) + 1

            return helper(amount)

Coin Change II (518) :: 2D in naive implementation

The key idea here is to solve an unbounded variant of the knapsack problem (unbounded because each coin (choice) can be used as many times as desired). The main part of this problem is to realise that it is indeed a 2D or whatever implementation, however, we can easily roll it up into a 1D array, we attempt to use each coin and update the partial sums we can create and in that way each coin can be used as many times as possible. dp[i] is the number of ways to make up that amount = i. Also realise that this a combination counting and we need to absolutely avoid double counting (and caring about permutations) that’s why the outer loop is on coins.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    class Solution:
        def change(self, amount: int, coins: List[int]) -> int:
            dp = [0] * (amount + 1)

            # trivial base: 1 way to have empty combi
            dp[0] = 1

            # iterates through each coin denomination. This ordering ensures combinations are counted without double counting combinations (because they are permuted differently) (crucial for problems counting combinations).

            for coin in coins:
                # use the same denom as many times as possible:
                for amt in range(coin, amount + 1):
                    dp[amt] += dp[amt - coin]

            return dp[amount]

by the way, this is how we can see the non-flattened 2D approach to connect the dots on how to flatten it into 1D:

2D definition:
dp[i][j] = number of ways to make up amount j using the first i coins (i.e., coins ) (slice)
This is the traditional “table” version before you flatten.
So, base cases:
For any i, dp[i][0] = 1 (There is exactly one way to make amount 0: take nothing.)
For dp[0][j] = 0 when j > 0 (With 0 coins, can’t form any positive amount.)
So our state transitions look like this:
dp[i][j]=dp[i−1][j]+dp[i][j−coins[i−1]] if j≥coins[i−1]
dp[i][j]=dp[i−1][j] if j<coins[i−1]
which gives the following 2D version of the code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    n = len(coins)
    dp = [[0] * (amount + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 1

    for i in range(1, n + 1):          # using first i coins
        for j in range(amount + 1):     # for each target amount
            if j >= coins[i-1]:
                dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]]
            else:
                dp[i][j] = dp[i-1][j]
and our answer would be at dp[n][target]
In the 1D flattening:
We roll up the i dimension (coins) into an update rule by ensuring we process coins one at a time and, for each coin, accumulate number of ways for all amounts in order.
The key is: for each coin, update dp[amt] += dp[amt - coin] iteratively for all amt ≥ coin.
That’s why we get:
1
2
3
4
5
   dp = [0] * (amount + 1)
   dp[0] = 1
   for coin in coins: # this is the "row" progression (when compared to the 2D version)
       for amt in range(coin, amount + 1):
           dp[amt] += dp[amt - coin]
The outer loop on coins is equivalent to the 2D DP’s row progression—each new coin can only build on results found so far, not reorder the combinations.

Partition Equal Subset Sum (416)

Target Sum (494)

We can solve this using a recursive approach, or we can rephrase the question into one that is a bounded knapsack problem where the LHS = RHS. 3 things to take note: the way we convert it into a bounded knapsack problem, the problem beinga combination sum problem, therefore we have to iterate over the options to avoid double counting and the order of traversal of the range (right to left).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
   # M1: Recursive solution:
   from functools import cache
   class Solution:
       def findTargetSumWays(self, nums: List[int], target: int) -> int:

           @cache
           def helper(idx, target):
               if idx == 0:
                   a, b = nums[idx], -nums[idx]

                   # trivial edge case when target = 0 then both will work and that's 2 wayss
                   if a == target and b == target:
                       return 2

                   return 1 if a == target or b == target else 0

               num = nums[idx]
               # choose this:
               pos_ways, neg_ways = helper(idx - 1, target + num), helper(idx - 1, target - num)

               return pos_ways + neg_ways

           return helper(len(nums) - 1, target)

   # M2: Iterative bottom up with space optimisation (1D array rollup that allows us to reduce space usage)
   class Solution:
       def findTargetSumWays(self, nums: List[int], target: int) -> int:
           # rephrasing the problem into a bounded knapsack problem.
           # we want to have LHS = RHS the target will also be split
           num_sum = sum(nums)
           total = (num_sum + target)
           if is_impossible:=(num_sum < abs(target) or total % 2 != 0):
               return 0

           knap_target = total // 2
           # we want to select subset such that we will reach knap_target.
           # dp[i] = num ways to reach target val = i
           dp = [0] * (knap_target + 1)
           dp[0] = 1

           # NOTE [1]: we wanna find the number of combis here, so we control the order of inclusion of nums so that we don't end up doing permutation_sum type and end up with double counting
           for num in nums:
               # NOTE [2]: the order here matters and we need to go from right to left (big to small) to avoid double counting.
               # for target_sum in range(num, knap_target + 1): # so this will be wrong
               for target_sum in range(knap_target, num - 1, -1):
                   gap = target_sum - num
                   dp[target_sum] += dp[gap]

           return dp[knap_target]

Ones and Zeroes (474)

Combination/Subsequence Counting #

Number of ways to achieve a target by combining elements, usually counting answers not optimizing them

Problems #

Decode Ways (91) This is a counting question, we just need to build onto previous subproblems’ counts. So for the iterative version, let dp[i] the number of ways of decoding up to index one. Remember to include values for the trivial empty string as well (which is why we fill up to idx n + 1).

Applying a more frameworked approach:

Subproblems: Number of ways to decode substring `s[:i]`.
Overlapping subproblems: Yes, decoding `s[:i]` depends on `s[:i-1]` and `s[:i-2]`.
Choices at each subproblem: Decode single digit or two digits.
DP Relation: \[ dp[i] = \mathbb{1}[s_{i-1} \neq 0] \cdot dp[i-1] + \mathbb{1}[10 \leq s_{i-2} s_{i-1} \leq 26] \cdot dp[i-2] \]
Independence: Each choice leads to subproblems that do not interfere.

The recurrence relation will tell us that we only need to consider 2 states each time, so we can use a 2-rolling-variable optimisation for the space.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
        # iterative without the rolling variable optimisation: =>
        class Solution:
            def numDecodings(self, s: str) -> int:
                # If the input is empty or starts with '0', there are no valid decodings.
                if not s or s[0] == '0':
                    return 0

                L = len(s)

                # dp[i] will store the number of ways to decode the substring s[:i]
                # We use length L + 1 to handle the base case for an empty substring
                dp = [0] * (L + 1)

                # Base cases:
                dp[0] = 1  # There's one way to decode an empty string (do nothing)
                dp[1] = 1  # Since s[0] != '0', there's one way to decode the first character

                # Loop through the string from position 2 onwards (1-based indexing in dp)
                for i in range(2, L + 1):
                    # Check if single digit decode is possible (last one digit)
                    # If s[i-1] is not '0', then we can decode it as a letter on its own
                    if s[i - 1] != '0':
                        dp[i] += dp[i - 1]  # Add the ways up to the previous position

                    # Check if two-digit decode is possible (last two digits)
                    two_digit = int(s[i - 2:i])
                    # If the two-digit number is between 10 and 26 inclusive, it can be decoded as a letter
                    if 10 <= two_digit <= 26:
                        dp[i] += dp[i - 2]  # Add the ways up to i - 2 position

                # The answer is the number of ways to decode the entire string s[:L]
                return dp[L]

        # so the 2 rolling variable optimisation is straightforward for us to see:
        # note the change in the iteration range because of the use of the roll-up variable.
        class Solution:
            def numDecodings(self, s: str) -> int:
                # Edge case: empty string or starting with '0' means no possible decoding
                if not s or s[0] == '0':
                    return 0

                prev = 1  # dp[0], ways to decode empty string
                curr = 1  # dp[1], ways to decode string of length 1 (assuming s[0] != '0')

                for i in range(1, len(s)):
                    temp = 0  # ways to decode up to position i+1 (1-based indexing)

                    # Check if single digit decode is valid (s[i] != '0')
                    if s[i] != '0':
                        temp += curr  # Can decode single char, so add ways till previous char

                    # Check if two-digit decode is valid (10 <= s[i-1:i+1] <= 26)
                    two_digit = int(s[i-1:i+1])
                    if 10 <= two_digit <= 26:
                        temp += prev  # Can decode two chars together

                    # If no valid decode for this position, temp will be 0 -> return 0 later
                    if temp == 0:
                        return 0

                    # Shift dp states for next iteration
                    prev, curr = curr, temp

                return curr


        # of course, we have the recursive solution as well:
        from functools import cache

        class Solution:
            def numDecodings(self, s: str) -> int:
                n = len(s)

                @cache
                def dfs(i):
                    if i == n:
                        return 1  # Finished decoding successfully
                    if s[i] == '0':
                        return 0  # Invalid

                    # Single digit decode
                    count = dfs(i + 1)

                    # Two digit decode if valid
                    if i + 1 < n and 10 <= int(s[i:i+2]) <= 26:
                        count += dfs(i + 2)

                    return count

                return dfs(0)

Also this is a good demonstration of the iteration ranges when we use rolling variable optimisations. See this table for more info:

Method	State/Indexing	Range	Rationale
DP Array	1-based, dp base	2 to L+1 (n+1)	Need the two previous for `dp[i]`, and there’s a dummy base at index 0
2-Variable Roll	0-based, positions	1 to L-1	Only need to look back two steps; base cases set up before loop

Combination Sum IV (377)

Longest Increasing Subsequence #

Problems #

Longest Increasing Subsequence (300)

This is a classic question, we have the slow 1D DP option and the patience sorting option to work with. The patience sorting option is useful for this because of the requirement that we need strictly increasing subsequences, so we’re almost playing the game of patience there. We just need to keep track of tails (smallest number in existing stacks) and spawn a new stack if the insertion index for it is not within the existing stacks. patience sorting version only works if we want to find the length of LIS, not the LIS itself (have to mod it).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    import bisect

    class Solution:
        def lengthOfLIS(self, nums: List[int]) -> int:
            tails = []  # tails[i] will hold the smallest ending number of an increasing subsequence of length i+1 (tail of a stack of cards)

            for x in nums:
                # Find the insertion point for x in tails to maintain sorted order
                # This corresponds to the leftmost pile top >= x (or new pile if none found)
                idx = bisect.bisect_left(tails, x)

                # CASE 1: add new pile:
                # If x is larger than all pile tops, create a new pile by appending it
                if idx == len(tails):
                    tails.append(x)
                else:
                    # CASE 2: replace within existing stack:
                    # Otherwise, replace the existing pile top with x
                    # This keeps tails optimized to have smallest possible tail elements
                    tails[idx] = x

            # Number of piles equals length of longest increasing subsequence
            return len(tails)

The patience sort version is optimal, but we can also employ a 1D-DP approach for this. dp[i] is the LIS for string formed by first i chars inclusive.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    class Solution:
        def lengthOfLIS(self, nums: List[int]) -> int:
            n = len(nums)
            # all init base to 1
            dp = [1] * (n)
            for right in range(1, n):
                for left in range(right):
                    # we have this window and we need to find out if nums[right] can be incremented (if any smaller elements exist in the window)
                    if nums[right] > nums[left]:
                        dp[right] = max(dp[right], dp[left] + 1)

            return max(dp)

DP with Rolling Variables / Space Optimization #

Reduce storage to minimal multi-var tracking

Problems #

Climbing Stairs (70) :: optimised
Min Cost Climbing Stairs (746) :: rolling two-variable method
Maximum Product Subarray (152) :: track max/min in constant space

Stock Trading and State-Machine DP #

Multi-state progression: hold, rest, cooldown, buy/sell with constraints

Problems #

Best Time to Buy and Sell Stock I (121)
Best Time to Buy and Sell Stock II (122)

Best Time to Buy and Sell Stock with Cooldown (309)

Here, cooldown adds a “memory” requirement: you must know the previous state’s action to decide the current. Thus, this problem essentially requires DP/state-machine or similar approach instead of simple greedy.

We know the there can be 3 possible states for every day, we have to track them all and comb through, on first instinct, we end up needing one array per state, but we can inspect it and know that we can just use 3 rolling variables instead.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
    # M1: without the space optimisations
    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            if not prices:
                return 0

            n = len(prices)

            # init 3-state dp:
            hold, sold, rest = [0] * n, [0] * n, [0] * n

            # init first vals, only hold matters, we can't sell that day
            hold[0] -= prices[0]

            for i in range(1, n):
                hold[i] = max(
                    hold[i - 1], # was holding yesterday also:
                    rest[i - 1] - prices[i] # cooldown ytd, can buy today
                )
                sold[i] = hold[i - 1] + prices[i] # held until ytd, sold today
                rest[i] = max(
                    rest[i - 1], # rested ytd also
                    sold[i - 1], # sold ytd, rested today
                )

            return max(
                sold[n - 1], # sold on the last day
                rest[n - 1] # rested on the last day
            )

    # M2: with the space optimisations:
    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            if not prices:
                return 0

            n = len(prices)

            # init 3-state dp:
            hold, sold, rest = -prices[0], 0, 0

            for i in range(1, n):
                # snapshot the old vals:
                p_hold, p_sold, p_rest = hold, sold, rest

                hold = max(
                    p_hold, # was holding yesterday also:
                    p_rest - prices[i] # cooldown ytd, can buy today
                )
                sold = p_hold + prices[i] # held until ytd, sold today
                rest = max(
                    p_rest, # rested ytd also
                    p_sold, # sold ytd, rested today
                )

            return max(
                sold, # sold on the last day
                rest # rested on the last day
            )

0/1 Knapsack and Bounded Subset Choices #

Single-use element selection, backward fill

Problems #

Partition Equal Subset Sum (416)

Yet another classic, we are asked to return True if there’s a partition of an array into 2 subsets such that we have equal sums. This is just a slight rewording of the classic 0/1 knapsack problem (because we either include or exclude choice that’s why 0/1). It’s a reword because if we find one subset, then we have also found the other subset (equalling to half of what we found).

For implementation, a 1D array approach is already a space optimised rolling approach. We need to be careful about how we build up values to avoid the double counting, which is why we need to work backwards on the dp array index for each num case (so as to not double-count multiple uses of num).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
    from typing import List

    class Solution:
        def canPartition(self, nums: List[int]) -> bool:
            total_sum = sum(nums)
            if total_sum % 2 != 0:
                return False  # sum is odd, cannot split equally

            target = total_sum // 2

            dp = [False] * (target + 1) # dp[i] is True if value = i can be achieved from summing elements within a subset.
            dp[0] = True

            # NB: inclusion / exclusion of number is classic for 0/1 bounded knapsack, that's why this is the outer for loop
            for num in nums:
                # iterate backwards to avoid reuse of the same item multiple times in the same iteration
                for i in range(target, num - 1, -1):
                    dp[i] = (
                        dp[i] # exclusion case
                        or
                        dp[i - num] # inclusion
                    )

            return dp[target]

Target Sum (494)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
    # M1: Recursive solution:
    from functools import cache
    class Solution:
        def findTargetSumWays(self, nums: List[int], target: int) -> int:

            @cache
            def helper(idx, target):
                if idx == 0:
                    a, b = nums[idx], -nums[idx]

                    # trivial edge case when target = 0 then both will work and that's 2 wayss
                    if a == target and b == target:
                        return 2

                    return 1 if a == target or b == target else 0

                num = nums[idx]
                # choose this:
                pos_ways, neg_ways = helper(idx - 1, target + num), helper(idx - 1, target - num)

                return pos_ways + neg_ways

            return helper(len(nums) - 1, target)

    # M2: Iterative bottom up with space optimisation (1D array rollup that allows us to reduce space usage)
    class Solution:
        def findTargetSumWays(self, nums: List[int], target: int) -> int:
            # rephrasing the problem into a bounded knapsack problem.
            # we want to have LHS = RHS the target will also be split
            num_sum = sum(nums)
            total = (num_sum + target)
            if is_impossible:=(num_sum < abs(target) or total % 2 != 0):
                return 0

            knap_target = total // 2
            # we want to select subset such that we will reach knap_target.
            # dp[i] = num ways to reach target val = i
            dp = [0] * (knap_target + 1)
            dp[0] = 1

            # NOTE [1]: we wanna find the number of combis here, so we control the order of inclusion of nums so that we don't end up doing permutation_sum type and end up with double counting
            for num in nums:
                # NOTE [2]: the order here matters and we need to go from right to left (big to small) to avoid double counting.
                # for target_sum in range(num, knap_target + 1): # so this will be wrong
                for target_sum in range(knap_target, num - 1, -1):
                    gap = target_sum - num
                    dp[target_sum] += dp[gap]

            return dp[knap_target]

Ones and Zeroes (474)

This question is a classic 0/1 bounded knapsack but with extra conditions to govern the choices, it’s the choices that effectively act as a “cost” (in the framing of the knapsack problem, where a choice has a cost). For each str in strs, we try to include or exclude it, we can only use a str once that’s why it’s a 0/1 knapsack. It’s very important for us to do the right to left sweeping else we won’t be able to enforce the single use constraint.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
    from typing import List

    class Solution:
        def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
            dp = [[0] * (n + 1) for _ in range(m + 1)] # dp[i][j] = largest subset with i 0's and j 1's in the subset.

            for s in strs:
                zero_count = s.count('0')
                one_count = len(s) - zero_count

                if zero_count > m or one_count > n:
                    continue

                # right to left for both choices because both cases are 0/1 use
                for zeros_left in range(m, zero_count - 1, -1):
                    for ones_left in range(n, one_count - 1, -1):
                        dp[zeros_left][ones_left] = max(
                            dp[zeros_left][ones_left], # start fresh
                            1 + dp[zeros_left - zero_count][ones_left - one_count] # accumulate
                        )

            return dp[m][n]

Complexity analysis:

Time and Space Complexity
Time complexity: O(L×m×n) where LL is the number of strings in strs, and m,nm,n are the allowed zeros and ones respectively. LL iterations for all strings, and within each, an O(mn) iteration for dp updates.
Space complexity: O(m×n) for the dp table.
Given constraints (m,n≤100m,L≤600), this is efficient enough for typical inputs.

Bitmask and State Compression DP #

State represented by bitmask or difference for subset/assignment/exact grouping

Problems #

⭐️Tallest Billboard (956)

This is wild, the first thing to notice is that many subsets share the same difference between them so we can consider keeping track of the differences that we find as we build things. That’s why dp{k:v} where k is the difference, d, between the sums of the two subsets formed so far and v is the max sum of the smaller subset amongst the two for this difference, d.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
    class Solution:
        def tallestBillboard(self, rods: List[int]) -> int:
            # dp{k:v} where k = d = diff b/w left and right poles (subsets); v = max sum of the smaller subset for the difference

            dp = {0:0} # trivial when both subsets are empty

            for rod in rods:
                # for each diff we encounter so far, we can do 3 things:

                # A: do not use the rod
                # B: use the rod, add it to the "taller" subset => this updates the differences from d to d + rod, no change to the smaller subset sum
                # C: use the rod, add it to the "shorter" subset => this updates the  diff to be |d - r| (short and tall may swap places)
                # eventually, answer will be max value within dp[0]

                copy = dp.copy() # copying keeps the changes unaffected across multiple cases. separates reads and writes.
                for d, smaller in dp.items():
                    # case A: no use:
                    copy[d] = max(copy.get(d, 0), smaller) # keep the bigger val
                    # case B: add to taller
                    copy[d + rod] = max(copy.get(d + rod, 0), 0, smaller)
                    # case C: add to the shorter one:
                    diff = abs(d - rod)
                    if d < rod:
                        updated_smaller = smaller + d
                    else:
                        updated_smaller = smaller + rod

                    copy[diff] = max(updated_smaller, copy.get(diff, 0))

                dp = copy

            return dp.get(0, 0)

Word Segmentation and Dictionary DP #

Segment string with a dictionary, reconstruct valid sentences

Problems #

Word Break (139)

This is about creating valid segments and there’s a lookup that we would need to do for validity checks. We are asked to find out whether we can segment for this version of the problem.

The substructure property is as such, if my last segment I can make from the right is legit, and the immediate left of that is also a valid segment then I’m fine with the whole segmentation process. dp[i] keeps track of whether a valid segment ends at ith idx.

We check out things using 2 pointers, i and j and fill up a 1D dp table for this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
       class Solution:
        def wordBreak(self, s: str, wordDict: List[str]) -> bool:
            wordSet = set(wordDict)  # O(1) lookup
            n = len(s)
            dp = [False] * (n + 1) # dp[i] = True if first i characters are segmentable
            dp[0] = True  # empty substring is segmentable

            max_word_length = max(map(len, wordDict)) if wordDict else 0

            for i in range(1, n + 1):
                # Limit left boundary (j) to speed up checks (optimization)
                for j in range(max(0, i - max_word_length), i):
                    if dp[j] and s[j:i] in wordSet:
                        dp[i] = True
                        break  # early break for efficiency, since we know that dp[i] is already a legit segmentation.

            return dp[n]

Word Break II (140)

This is a mix of approaches, it’s somewhat tedius but not difficult to consider if we think calmly and strategise based on the information that we need. For the sentence accumulation, we know that it’s a matter of exploring decision curves (break here as a fork between multiple sentences?…) so it’s a backtracking that we need to do.

The backtracking can be assisted by a helper DP array or we may directly rely on memoised calls to a backtrack function.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
    # V2: bottom up, dp-assisted
    from typing import List
    from functools import cache

    class Solution:
        def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
            """
            This question is a mix of multiple approaches.

            {preprocessing}

            1. we need to know about "segmentability" i.e. can i segment at this location?  ==> this is what we can use a DP for

            2. need info on where I could have started from given ith idx is the end-segment. ==> need to know valid_starts

            {gathering the sentences}
            1. we start from the right possible index for spaces, then we explore the different approaches and gather a path.

            this is a decision tree traversal, so it's dfs-like / backtracking that we're doing here
            """
            n = len(s)
            wordset = set(wordDict)

            # so dp[i] ==> I can segment at ith idx (for insertion point)
            dp = [False] * (n + 1)
            dp[0] = True # vacuous truth

            # valid starts is going to be a list of lists, it means that ith idx is the end, and keeps track of where we could have started from.
            valid_starts = [[] for _ in range(n + 1)]

            for i in range(1, n + 1): # i is the right exclusive idx for slicing, hence goes till i = n
                for j in range(i): # j is the left inclusive idx for slicing
                    if dp[j] and s[j:i] in wordset:
                        dp[i] = True
                        valid_starts[i].append(j)

            if not dp[n]: # early returns for can't segment
                return []


            """
            After preprocessing, now we can backtrack:
            """
            @cache
            def backtrack(end):
                # end states:
                if end == 0: # i.e. reached the starting idx
                    return [""]

                sentences = []
                for start in valid_starts[end]:
                    word = s[start:end]
                    prefixes = backtrack(start)
                    for prefix in prefixes:
                        if prefix:
                            sentences.append(f"{prefix} {word}")
                        else: # for the empty string case @ terminus (starting idx = end = 0)
                            sentences.append(word)
                return sentences

            return backtrack(n)

and this is the merely memoised approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
    from functools import cache

    class Solution:
        def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
            wordSet = set(wordDict)

            @cache
            def backtrack(start_idx):
                # end-cases:
                if start_idx == len(s):
                    return [""] # trivially, we return a sentence with empty string

                res = [] # sentences to form starting with start_idx
                for end in range(start_idx + 1, len(s) + 1):
                    word = s[start_idx:end]
                    if not word in wordSet:
                        continue

                    # we can backtrack now:
                    choices = backtrack(end)
                    for sub in choices:
                        if sub:
                            res.append(f"{word} {sub}")
                        else: # current word is last word
                            res.append(word) # this is the last word in the sentence
                return res

            return backtrack(0)

SOE #

Rolling variable optimisations typically also involve changes to the iteration range, be careful on that. See this elaboration:

  The **difference in the iteration range** between the DP array version and the two-variable ("rollup") version comes down to two things: **indexing conventions** and how you track the "state" across iterations.

  ***

  ## Array DP Version (`dp` array)

  - The `dp` array is of length `L+1`, where `dp[i]` means: "number of ways to decode the substring `s[:i]`".
  - You initialize `dp = 1` (empty string), and `dp = 1` if the first character is valid.[1]
  - The loop runs from `i = 2` to `L` (i.e., `range(2, L+1)`), and you check the last one or two digits ending at index `i-1` and `i-2`.
  - This is **1-based** with a "dummy" base at `dp`, so you need to go all the way to `L`.

  ***

  ## Two-Variable Rolling Version

  - Instead of keeping a full array, you only keep enough history for two previous states (`prev`, `curr`) — which correspond to `dp[i-2]` and `dp[i-1]`, respectively.
  - You start at `i = 1` and go to `len(s)-1` (so `range(1, len(s))`), since:
    - At each index `i`, you're considering the substring ending at `s[i]`, which, with Python's slicing, aligns with how you retrieve the digits for single-digit and two-digit checks: `s[i]` and `s[i-1:i+1]`.
  - The initialization lines (`prev = curr = 1`) handle the base cases for the empty prefix and the first digit, so your loop can safely start at index 1 (second character of `s`).

  ***

  ## Why the ranges differ:

  - **DP Array:** Needs to cover all possible string positions in a 1-based approach due to the extra initial base state.
  - **Rolling Variables:** Tracks only the minimal required info, and because of how states are rolled forward, the effective start point is different (starts after the very first character).

  ***

  ## Summary Table

  | Method         | State/Indexing      | Range              | Rationale                                 |
  |----------------|---------------------|--------------------|--------------------------------------------|
  | DP Array       | 1-based, dp base | 2 to L+1 (n+1)     | Need the two previous for `dp[i]`, and there's a dummy base at index 0 |
  | 2-Variable Roll| 0-based, positions  | 1 to L-1           | Only need to look back two steps; base cases set up before loop          |

  ***

  This convention is common in rolling/compressed DP: **the rolling index starts later because the base cases (`prev`, `curr`) are set up before the loop, and you always have at least two characters to look back on**. This minimizes storage but shifts the loop start point.

  References and further reading:
  - AlgoMonster explanation[1]
  - Tom VanAntwerp Leetcode DP breakdown[2]
  - YouTube walkthroughs[4]

  [1](https://algo.monster/liteproblems/91)
  [2](https://tomvanantwerp.com/coding-questions/leetcode-091-decode-ways/)
  [3](https://jzleetcode.github.io/posts/leet-0091-hackerrank-ascii-encoded-strings/)
  [4](https://www.youtube.com/watch?v=Jx05Y5t3eg0)
  [5](https://www.reddit.com/r/leetcode/comments/1ae0wpa/understanding_recursive_solution_to_decode_ways/)
  [6](https://www.youtube.com/watch?v=FEkZxCl_-ik)
  [7](https://benzene-dev.tistory.com/123)
  [8](https://wentao-shao.gitbook.io/leetcode/dynamic-programming/1.position/91.decode-ways)

Incorrect base case initializations
Wrong iteration order leading to overwriting valid states
Misinterpretation of state meaning or transition relationship
Multiplying negative numbers:
- if we’re seeking to find out an eventual max, we need to keep track of both min negative number and max positive number if we care about their products
  for product-related accumulators, remember that we would likely have to handle both positive and negative accumulators (high, low) because if we do negative operands, then the negative value (low) might flip and become a large positive!
  this is seen in the “Maximum Product Subarray” question.

Decision Flow #

Is problem about sequential optimal choice? → DP
Want space-optimized solution? → Rolling array techniques
Complex constraints or multiple states? → Multi-dimensional DP

Style, Tricks and Boilerplate #

Style #

I think in general, it’s a good idea to just do the first-reach 2D tables and then look for space optimisations.
When working with 2D tables, just define the length/breadth symbols being used via comments to prevent getting confused.
I think it’s VERY IMPORTANT to define the meanings of i and j and the table dimension meanings when writing out the answer so that we don’t end up wasting time rethinking that part or worse, getting confused.
the determining of filling order and state transitions also becomes easier.
General rule of thumb for space optimisations The general rule of thumb (for flattening 2D into 1D state tracking)
- 0/1 knapsack (each item once) \(\implies\) iterate capacity/target backwards so you don’t reuse the same item in one iteration. (this is for the 1D array rollup)
- Unbounded knapsack (items unlimited) \(\implies\) iterate forwards so that the newly updated states can be reused immediately for multiple copies of the same item.
- Combination counting with unlimited reuse (coin change) \(\implies\) coins outer loop, amount inner loop forward.
- Combination counting with one-use-only (subset sum) \(\implies\) nums outer loop, amount inner loop backward.

Tricks #

DP questions often init array with 1 extra to account for empty / vacuous truths
You created dp = [[] for _ in range(L)] but often DP arrays are sized L+1 to handle empty prefix easily.
However, remember that if we find a way to do rolling variables, it may not be the same iteration range.
edge-padding is useful when handling sentinel values like at border-elements. This can be seen in the “Burst Balloons” question. Also kind of related to the largest rectangle question that we have seen before.

Tricks relating to recurrence formulae #

circular to linear array is a matter of entertaining 2 mutually exclusive events.
in the case of house robber II vs house robber I, we realise that it’s a matter of reducing the problem from circular to straight arrays. Literally just array splicing in the context of the contraints given.
In the case of Longest Palindromic Substring, it’s a matter of tracking contiguous regions which makes it feel 2-dimensional.
What are the 2 dimensions? Can we find equivalent but different ways of representing the state equations? Yes We can let the substrings (continuous) be defined by left,right pointers. We can ALSO let it be defined by left, length instead.

Python #

memoise functions using the @cache decorator, all arguments must be hashable.

Boilerplate #

Patience Sorting #

When doing LIS problems, we can find a linear time solution by using Patience sorting.

The easiest way to reason this is to just think about keeping track of piles of numbers that are increasing subsequences and just tracking the tail of that number.

A tail is the smallest value in that pile of numbers.

So we usually have 2 options for a particular number:

it gets added to an existing pile
- it may possibly become a new tail within an existing pile
it starts a new pile
- if the new number doesn’t fit with any of the existing tails (existing min values for the existing piles) then it should start a pile of its own.

Finally, we know that we can join up at least one element from each pile to form the longest increasing subsequence.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
import bisect
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []
        for x in nums:
            # left most place to keep x within tails
            # this picks the currently accumulating pile / stacks
            # so tails[k] is giong t obe the smallest possible value of increasing subsequence of length (k + 1)
            idx = bisect.bisect_left(tails, x)
            if should_create_new_stack:=(idx == len(tails)): # can create a new stack
                tails.append(x)
            else:  # replace within an existing stack's min (represents top of the stack)
                tails[idx] = x

        return len(tails)

TODO Pending tasks `[0/0]` #

Niche patterns from CP algos:
1. Subset over Sum DP (this is a bitmasking pattern where the subsets are bitmask subsets.)

Canonical Question Types #

Linear State Transitions (Fibonacci-like) #

Problems #

Non-Adjacent Selection (House Robber type) #

Problems #

Maximum Subarray/Product/Range #

Problems #

Knapsack/Subset Sum Variants #

Problems #

Combination/Subsequence Counting #

Problems #

Longest Increasing Subsequence #

Problems #

DP with Rolling Variables / Space Optimization #

Problems #

Stock Trading and State-Machine DP #

Problems #

0/1 Knapsack and Bounded Subset Choices #

Problems #

Bitmask and State Compression DP #

Problems #

Word Segmentation and Dictionary DP #

Problems #

SOE #

Decision Flow #

Style, Tricks and Boilerplate #

Style #

Tricks #

Tricks relating to recurrence formulae #

Python #

Boilerplate #

Patience Sorting #

TODO Pending tasks [0/0] #

TODO Pending tasks `[0/0]` #