Topic 12: 1D DP

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

Typically, they involve some sort of optimisation problem that we’re interested in and we’re usually concerned with some order statistic instead of permuting or finding combinations here – e.g. min sum vs configuration that gives the min sum.

Counting problems may be optimised with this as well, especially if there’s a whole host of overlapping sub-problems, the calculation for which we can do smartly.

Read the notes below for a run-down.

Canonical Question Types #

Linear State Transitions (Fibonacci-like) #

• Progression by fixed window of previous states
• most of them can consider state roll-ups to reduce the space usage – it’s clearer depending on the general recursive formula we get (how \(k + 1\) relates to \(k\))

Problems #

1. 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.

   NB: it’s better to work towards the rolled-up version because it’s clearer that way.

   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)

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))

3. 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 #

1. 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)

2. 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.

   In most cases, we’re interested in how our problem is an evolution of a related problem. Here, we can try to make a circular array behave like a linear array precisely because we can break it down into 2 mutually exclusive cases (first house considered vs first house NOT considered.)

   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)
• We can consider this because of the associative nature of the operations
• For contiguous subarray sums, Kadane is usually a first-thought, works with negative numbers as well.

Problems #

1. 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. It technically is, because at each step, we choose whether to continue from before or start anew.

   We might be also 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

2. Maximum Subarray (53) – Kadane algo At each index I track the best subarray sum ending here — it’s either this element alone, or this element appended to the best ending at the previous index. I keep a global max of all these. One pass, O(1) space.

   Recognition Signals

   • “contiguous subarray” + optimise some cumulative score
   • No constraint on minimum length (if there were, you’d need a deque/prefix-sum variant)
   • Values can be negative (otherwise a simple total sum works)
   Anti-signals (when NOT to use the Kadane approach)

   • Subsequences (non-contiguous) — use a different DP state
   • Need the actual subarray indices — Kadane still works but you track start/end pointers
   • Circular array — use Kadane + total_sum minus min_subarray (LC 918)
   • At-most-K length constraint — need sliding window with monotonic deque (LC 862)

   There’s a couple of ways to do this, though Kadane-algo should be the first-reach algo for us:

   M1: Realising that it’s DP, specifically Kadane Algo

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

   class Solution: def maxSubArray(self, nums: List[int]) -> int: """ This is straight up just Kadane Algo: 1. we care about inclusion or exclusion. 2. elements can be negative Thinking of it as a state-tracing 1D DP isn't that far off though. We can realise that it's Kadane-by focusing on the substructures and then emphasising the contiguious nature of the problem. Fastest recognition heuristic: "contiguous subarray" + "maximise sum" + values can be negative → Kadane, immediate. """ best_ending_here = nums[0] global_best = nums[0] for num in nums[1:]: best_ending_here = max(best_ending_here + num, num) # build onto, include num OR start fresh global_best = max(global_best, best_ending_here) return global_best

   M2: divide and conquer approach, which we see the problem as having 2 parts: left and right partschinite

   It’s recursive,

   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

   from typing import List class Solution: def maxSubArray(self, nums: List[int]) -> int: def helper(left: int, right: int) -> int: # Base case: single element if left == right: return nums[left] mid = left + (right - left) // 2 # Maximum subarray in left half left_max = helper(left, mid) # Maximum subarray in right half right_max = helper(mid + 1, right) # Maximum subarray crossing mid cross_max = max_crossing_subarray(left, mid, right) # Return overall max return max(left_max, right_max, cross_max) def max_crossing_subarray(left: int, mid: int, right: int) -> int: # Find max subarray sum crossing mid, including mid left_sum = float('-inf') curr_sum = 0 for i in range(mid, left - 1, -1): curr_sum += nums[i] if curr_sum > left_sum: left_sum = curr_sum right_sum = float('-inf') curr_sum = 0 for i in range(mid + 1, right + 1): curr_sum += nums[i] if curr_sum > right_sum: right_sum = curr_sum return left_sum + right_sum return helper(0, len(nums) - 1)

   There’s also some common misconceptions:

   if stuck @ state definition

   ask “what does it mean for a subarray to end at position i?” It means every element from some start index to i is included — no gaps. So the only state you need is: “what is the maximum sum subarray that ends exactly here?” That’s one number, not two.

   how to decide whether to extend or restart?

   extending is prev_ending_here + curr; restarting is curr alone. You take the max. If the running sum was negative, restarting always wins.

   stuck @ global ans update?

   after every element, compare ending_here to global_best. One line

   Finally, there are ways to transform this, Kadane is simpler to imagine its transformations

   transformations

   • Circular array (LC 918): the optimal subarray can wrap. Kadane gives you the non-wrapping case; total_sum minus min_subarray (run Kadane with inverted signs) gives the wrapping case. Your circular-subarray work in canonicals.org covers this.

   • All elements positive: Kadane degenerates — best_ending_here never resets, so the answer is always the total sum. Knowing this degenerate case sharpens the intuition for why negatives are the crux.

   • Online/streaming: Kadane is already online — you only need O(1) state. No issue. If you additionally need to answer “max subarray ending exactly here” as a query, you emit best_ending_here after each step.

   • 2D generalisation (max sum rectangle, LC 363): compress row pairs into a 1D column-sum array, then run Kadane. This is a non-trivial but direct extension.

Combination/Subsequence Counting #

• Number of ways to achieve a target by combining elements, usually counting answers not optimizing them
• combination counting is about iterating over the options as the outer loops so that we don’t end up doing double counting
• when doing this, the order of traversing each option-dimension is the same.

Problems #

1. 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).

   we go left to right because we can use the previously built values for the future ones (right values can be built using left values).

   Applying a more frameworked approach to understanding this

   • 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 tells us that we only need to consider 2 states each time, so we can use a 2-rolling-variable optimisation for the space.

   iterative approach,without the rolling variable optimisation and the equivalent form of rolling it up into 2-vars

   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

   # 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]

   Code Snippet 1: iterative form, no rolling variable optimisation

   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

   # 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

   Code Snippet 2: converting it into a rolled up variable form

   Here’s the rolled up solution:

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

   class Solution: def numDecodings(self, s: str) -> int: # the main choice is whether i can be a one-fer or two-fer, if at all # dp[i] = ith place how many # recurrence: A) cannot 1fer and cannot 2-fer B) can 1 fer but not 2fer C: can 1fer or 2fer n = len(s) if n == 1: return 0 if s == '0' else 1 if n >= 2 and 1 <= int(s[:2]) <= 9: return 0 prev, curr = 1, 1 for i in range(1, n): # NOTE: here, i represents the calculation up to idx i of string s. so if we calculate i, means s[:i + 1] has been calculated. can_2fer = 10 <= int(s[i - 1: i + 1]) <= 26 # this accounts for the leadings zeros cases also, since it's a space over a bunch of digits adn we're only concerned if it has a 2fer value (which is bound by the double digits ascii charset for alphabetical chars) can_1fer = 1 <= int(s[i]) <= 9 if not (can_2fer or can_1fer): return 0 prev, curr = curr, (prev if can_2fer else 0) + (curr if can_1fer else 0) return curr

   We can choose to solve this via a dfs approach as well since this is about exploring paths.

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

   # 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

2. Combination Sum IV (377) This is such a juke. This is badly named. Look at the inputs and realise that it’s actually an unbounded knapsack problem where we need to do permutation counting (not combination counting).

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

   class Solution: def combinationSum4(self, nums: List[int], target: int) -> int: """ Combination counting! -- but this is a juke, it's actually permutation counting It's an unbounded knapsack. dp[i] = the number of permutations that add up to i -- it's 1-indexed so the answer will be at dp[target] we iterate the outer loop over the nums since it's combination counting loop order doesn't matter here because we can take any number for any number of times """ dp = [0] * (target + 1) dp[0] = 1 # k 1 way to make nothing for partial_sum in range(1, target + 1): # targets outer: permutation counting for num in nums: if partial_sum - num >= 0: dp[partial_sum] += dp[partial_sum - num] return dp[target]

Longest Increasing Subsequence #

Problems #

1. 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).

   The optimal patience sort approach works like so, in \(O(nlogn)\) time

   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 length of LIS for string formed by first i chars inclusive. This runs in \(O(n^{2})\)

   1 2 3 4 5 6 7 8 9 10 11

   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)

2. TODO LC 673 Number of LIS

3. TODO LC 1964 Find the Longest Valid Obstacle Course

Stock Trading and State-Machine DP #

• This canonical group was supposed to revolve mainly around the use of FSMs in solving some problems – the stock trading family of problems ends up being a really good reference for this .

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

Problems #

1. 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.

   without the space optimisation

   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

   # 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 )

   Adding in the state rollups:

   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

   # 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 )

Knapsack/Subset Sum Variants #

• In knapsack problems, we’re interested in whether to take or not take things (and put them in our knapsack.)

• Knapsack problems can be bounded (limited by the number of times a choice can be made) or unbounded choices (unlimited), partitioning, subset formation

• within this, we might try to do counting (of combinations…), optimising some statistic based on counts, or try to determine a predicate outcome (e.g. whether a pattern can be formed)

Problems #

1. Coin Change (322)

   This is a optimisation problem AND there’s more than one way to do the coin changing (so equivalent paths in the decision-tree) and that’s why it’s more of a DP than a greedy approach that we adopt..

   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

   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

   # 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

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

   # 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)

2. Coin Change II (518) :: 2D in naive implementation, 1D rollup easy – is a combination counting problem

   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. We introduce the coin denominations one by one because we only care about combinations.

   This allows us to introduce coin by coin (combination) instead of caring about when they’re introduced (permutations).

   Loop order is left to right because we can use the left sub-answers to build the right sub-answers.

   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]

   Code Snippet 3: bottom-up, iterative solution
   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.

3. Target Sum (494) – bounded 0/1 Knapsack Problem

   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.

   the recursive approach:

   The idx here within the helper is a choice index, it’s the current element that we have to make a choice on, we’re once again going from right to left of the options.

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

   # 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)

   3 things to take note:

   1. the way we convert it into a bounded knapsack problem — it’s because we realise that it’s an inclusion / exclusion decision that we’re doing AND we’re building up to a value.
   2. the problem being a combination sum problem, therefore we have to iterate over the options to avoid double counting
   3. and the order of traversal of the range (right to left) – this is because we only have a bounded 0/1 inclusion – so going right to left only allows us to do single inclusions (or exclusions) and avoids any sort of double counting / reuse of an element.

      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

      # 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]

0/1 Knapsack and Bounded Subset Choices #

1. Loop structure matters a lot here for knapsack-style DP questions:

   1. Bounded (0/1) or unbounded? \(\Rightarrow\) 0/1: inner loop backward \(\Rightarrow\) unbounded: inner loop forward

   2. Counting combinations or permutations? \(\Rightarrow\) combinations: items (nums) in outer loop, targets in inner \(\Rightarrow\) permutations: targets in outer loop, items in inner These two decisions are independent and compose.

      • Target Sum is 0/1 (backward inner) + combination count (nums outer).

      • Coin Change II (LC 518) is unbounded (forward inner) + combination count (coins outer).

        Getting these wrong produces a solution that passes most cases but fails on inputs with repeated elements.

2. permutation vs combination count

   Table 1: 2axes: boundedness vs permutation/combination counting

   counting objective	bounded 0/1 each item once	unbounded (items reusable)
   combination	nums outer, targets backward	nums outer, targets forward
   permutation	targets outer, nums backward *	targets outer, nums forward

   The * cell (bounded permutation) is rare and mostly doesn’t appear in LC, but the table is complete.

   [permutation count:]

   • If you loop: for target in range(...): for num in nums:
     • each target sum is built up by trying all nums in sequence for each partial target. The same subset {a, b} can be counted as (a then b) and (b then a) separately. You get permutation count.

   [combination count:]

   • If you loop: for num in nums: for target in range(…):
     • you fix the order in which nums are introduced. A subset can only be assembled in the order nums appears in the outer loop. {a, b} is only ever counted once. You get combination count.

3. The generalisation worth internalising: the 0/1 backward-sweep rule extends to as many dimensions as you have independent resource constraints.

   • Two budgets → 2D table, both loops backward.
   • Three budgets → 3D table, all three loops backward. The rule doesn’t change; only the number of nested loops scales.

Problems #

1. 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]

2. Target Sum (494) – bounded 0/1 Knapsack Problem 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.

   the recursive approach:

   The idx here within the helper is a choice index, it’s the current element that we have to make a choice on, we’re once again going from right to left of the options.

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

   # 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)

   Why is the outer loop is on the nums and the inner loops is on the target values – combinations vs permuatations

   This controls whether you count combinations or permutations.

   [permutation count:]

   • If you loop: for target in range(...): for num in nums:
     • each target sum is built up by trying all nums in sequence for each partial target. The same subset {a, b} can be counted as (a then b) and (b then a) separately. You get permutation count.

   [combination count:]

   • If you loop: for num in nums: for target in range(…):
     • you fix the order in which nums are introduced. A subset can only be assembled in the order nums appears in the outer loop. {a, b} is only ever counted once. You get combination count.

   This problem asks for ways, which is combination count. So nums is the outer loop. This is not specific to target sum — it is the general rule for any “count subsets” DP.

   3 things to take note:

   1. the way we convert it into a bounded knapsack problem — it’s because we realise that it’s an inclusion / exclusion decision that we’re doing AND we’re building up to a value.
   2. the problem being a combination sum problem, therefore we have to iterate over the options to avoid double counting
   3. and the order of traversal of the range (right to left) – this is because we only have a bounded 0/1 inclusion – so going right to left only allows us to do single inclusions (or exclusions) and avoids any sort of double counting / reuse of an element.

      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

      # 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]

3. 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 that is at the heart of this 0/1 family of problems.

   solution with extended working

   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

   class Solution: def findMaxForm(self, strs: List[str], m: int, n: int) -> int: """ We know that this is a 0/1 bounded knapsack problem, it's the unique costs that we need to account for. Let's do the 2D version first dp[i][j] = size of largest subset with i0s and j1s (1-indexed) So the ans will be at dp[m][n] Since it's a subset, it's a combination that we're focused on so it's combination counting. """ dp = [[0] * (n + 1) for _ in range(m + 1)] dp[0][0] = 0 # since we're doing combination counting, we go through the options: for s in strs: zero_count = s.count('0') one_count = len(s) - zero_count if zero_count > m or one_count > n: # if out of bounds, can't try including this. continue # now we do the 0/1 inclusion, it's on two different dimensions, so we right to left on both for balance_m in range(m, zero_count - 1, -1): for balance_n in range(n, one_count - 1, -1): gap_m, gap_n = balance_m - zero_count, balance_n - one_count dp[balance_m][balance_n] = max ( # exclusion case: keep the best subset achievable without this string dp[balance_m][balance_n], # accumulate using this: 1 + dp[gap_m][gap_n] ) 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.

   1 2 3 4 5 6 7 8 9

   def findMaxForm(self, strs, m, n): dp = [[0] * (n + 1) for _ in range(m + 1)] for s in strs: zeros = s.count('0') ones = len(s) - zeros for i in range(m, zeros - 1, -1): for j in range(n, ones - 1, -1): dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones]) return dp[m][n]

   Code Snippet 4: extra conditions and dimensions still get traversed right to left

Non-standard State Representation / Compression DP e.g. bitmasking ⭐️ #

• When it comes to state compression, we’ve seen the dimensional flattening that happens when we roll-up variables, that’s a decent bucket. There’s other approaches to, such as:
  • using bitmasks to represent state
  • rethinking what state we should be keeping track of and using something like a map for it
• State represented by bitmask or difference for subset/assignment/exact grouping

Problems #

1. Number of Unique Good Subsequences (1987)

   If we explore the non compressed version, we know that it’s a subsequence counting, so dp[i] = (# good seqs ending with 0, # good seqs ending with 1, has_encountered_0_before)

   The has_encountered_zero_before just helps us to know if "0" can be a good subsequence or not.

   As for the state transitions:

   1. if curr is 1: then we can end it with 1 for whatever we are accumulating so far

   2. if curr is 0: then we can only add that to those that end with 1 (to avoid leading zeroes)

      Then we realise that we can just a triple of rolling variables based on the state transitions.

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

      class Solution: def numberOfUniqueGoodSubsequences(self, binary: str) -> int: MOD = 10**9 + 7 count_end_with_0 = 0 count_end_with_1 = 0 has_zero = False for ch in binary: if ch == '1': # Append '1' to all subsequences (ending with 0 or 1) + start new subsequence '1' count_end_with_1 = (count_end_with_0 + count_end_with_1 + 1) % MOD else: # Append '0' only to subsequences ending with '1' has_zero = True count_end_with_0 = (count_end_with_0 + count_end_with_1) % MOD # sum subsequences ending with 0 and 1 plus subsequence "0" if exists return (count_end_with_0 + count_end_with_1 + (1 if has_zero else 0)) % MOD

2. ⭐️Tallest Billboard (956) (represent via map)

   step-by-step building up to the ans intuition

   This feels less like magic if we start with the brute force and watch what structure emerges.

   [ 1. consider the brute force ]

   1. for each rod, we have 3 options: (so \(n\) rods give \(3^{n}\) assignments)

      1. don’t use it
      2. add to the left pile that is being built
      3. add to the right pile that is being built

   2. in the brute force approach, the answer is the height of the shorter pile when both piles are of equal height \(\implies\) largest value of min(left, right) where left === right

   3. brute force won’t be enough because we have \(n\) at most 20 and that’s in the billions \(\implies\) we need to look for pruned approaches – there’s a lot of duplicate effort beacuse of overlapping subproblems

   [ 2.Rethink the state representation ]

   1. what’s important to track?
      • NOT: which pile a specific rod went to – so the choices are irrelevant to track
      • YES: r/s between the two pile heights is what is important – so each rod, has 3 decisions :
        1. accumulate discrepancy (add to larger, make it a bigger gap between smaller and larger)
        2. reduce the discrepancy (add to smaller, so that diff is reduced)
        3. don’t use it – discrepancy remains as is
   2. how to track?
      • diff and height of smaller stack is sufficient \(\implies\) 2 variables are sufficient.
      • so state is just a (diff, short)
      • given sum of rod heights based on inputs is at most 20 * 1000 = 20000, then we can have 20k distinct d-values
      • For each d, we want the max possible short length – that’s how we track it
      • compression:
        • instead of : tracking every (d, short) pair
        • we shall track: dp[d] = max short achievable for this difference \(\implies\) 1 number per difference value.
   3. state space collapse is from \(3^{n}\) to \(O(sum of rods)\)

   [ 3. Understanding the Transitions ]

   1. if existing state is dp[d] = smaller.
      • somewhere in the rods processed so far, we have assignment where tall - short = d and short = smaller, so tall = smaller + d.
   2. for new rod in consideration: 3 options
      1. skip it dp[d] unchanged
      2. add to taller pile – gap widens so new state: dp[d+ rod] = smaller
      3. add to shorter pile: we have 2 sub-cases

         1. rod < d : gap shorter, no flipping

         2. rod >= d: flipping of short and tall

            we can collapse this into: new_diff = abs(d - rod), new_smaller = smaller + min(d, rod)

   [ 4. Filling order caveats ]

   1. to avoid mixing up the state across two iterations, use the copy trick to separate reads and writes.
   general building up to the main answer

   The unlock sequence:

   1. Brute force is 3ⁿ. What am I tracking? Left sum and right sum — two numbers.

   2. Can I compress? I don’t need both absolute values.

      I need their difference and one of them.

      Pick the smaller one because that’s what the answer asks for (answer is dp[0]).

   3. What’s the state space of differences? Bounded by total rod length. Much smaller than 3ⁿ.

   4. Write dp as a map from difference to max-smaller. Transitions follow from “what happens to (d, smaller) when I add a rod to tall, short, or neither.”

   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 #

1. Word Break (139) all about segmentability

   1. We are asked for whether a solution exists, not asked for the best solution – we can explore non-greedy approaches. Also, we realise that we need to build up to an optimal answer for the question, so that’s why we go left to right on the string-indices.

   2. 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.

   3. The substructure property is as such,

      1. 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.
      2. dp[i] keeps track of whether a valid segment ends at ith idx (follow pythonic convention, exclusive range).

      The j marker exists because for s[i] to be a segmentable point, we need to look to its left to:

      1. find a segment point (j) that is valid AND
      2. the remaining slice has to be a valid word (i.e. s[j:i] to be a valid word)

      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]

   4. max_word_length optimisation:

      • Since we know that the search space of words is fixed, we know that the values for j are bounded, so we can be strict about how many possibilities to search.
        • The justification is: s[j:i] can only be in the wordset if its length is at most max_word_length, so any j further left than i - max_word_length can never produce a valid word.

2. 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. Word Break I answers a yes/no question. Word Break II asks for all valid segmentations. The moment the answer is a list of all solutions, backtracking is implicated — you cannot avoid enumerating the decision tree. DP alone cannot accumulate variable-length structured outputs like sentences.

   1. phase 1 (DP pre-processing) To create sentences, we need to consider segmentability, and that’s what Word Break I (139) deals with – so we have a way to use DP on this. That becomes a pre-processing step for us, and the DP array ends up being an intermediate info that we use.

   2. phase 2: backtracking

      For the sentence accumulation, realise that it’s an accumulation, we want all the configs – it’s going to be a costly algo, like backtracking.

      • – 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. Every segmentable index is a n-ary choice – each possible word is a start there. Branching factor is bounded by the number of words in the dictionary whose prefix matches the current position

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, which is easier to think of first:

 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)

DP with Rolling Variables / Space Optimization #

• Reduce storage to minimal multi-var tracking
• typically rolling of variables is something we use to do space usage optimisations – so this category isn’t exactly a self-standing one, that’s why the problems below have been out-linked to other sites
• it’s easier to intuit how to do the space-saving once we inspect the recurrence relationship, especially the generic one that shows how the \(k + 1\) case relates to the \(k\) case.

Problems #

1. Climbing Stairs (70) :: optimised
   • see answer above in linear state transitions
2. Min Cost Climbing Stairs (746) :: rolling two-variable method
   • see answer above in linear state transitions
3. Maximum Product Subarray (152) :: track max/min in constant space
   • see answer in the max subarray product range problems

SOE #

1. 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.

   1. 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.

   2. 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 2 3 4 5 6 7 8

2. Incorrect base case initialisation

3. Wrong iteration order leading to overwriting valid states

4. Misinterpretation of state meaning or transition relationship

5. 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 #

1. Is problem about sequential optimal choice? \(\Rightarrow\) DP
2. Want space-optimized solution? → Rolling array techniques
3. subarray related (contiguous) and operation in consideration is associative \(\Rightarrow\) optimal substructure shown \(\Rightarrow\) explore the substructure property, what needs to be tracked? If it’s left and right boundaries \(\Rightarrow\) 2D DP, else might be a smaller dimension too
4. Complex constraints or multiple states? → Multi-dimensional DP
5. “contiguous subarray” + “maximise sum” + values can be negative → Kadane, immediate.

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 #

1. 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.

2. 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.

3. avoiding the double counting when doing state compressions

   1. for cases like the 0/1 bounded knapsack, when we’re using arrays, we end up with the heuristic that “we iterate from right to left so that we can avoid double counting – because it’s a 0/1 inclusion / exclusion that we care about”.

   2. for other datastructures for the state management:

      • a dictionary \(\implies\) there’s a need to separate the reads from the writes during the iteration.

        example: tallest billboard (956) where we use a dictionary, we need to do the dictionary copying so that reads and writes are separated across iteration boundary

        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)