1D Dynamic Programming

1. 1.Climbing Stairs
   dp[i] = dp[i-1] + dp[i-2] with O(1) space optimizationeasy
2. 2.Min Cost Climbing Stairs
   dp[i] = cost[i] + min(dp[i-1], dp[i-2])easy
3. 3.House Robber
   Take vs Skip: dp[i] = max(dp[i-1], nums[i] + dp[i-2])medium
4. 4.House Robber II
   Circular array: run House Robber on 0..N-2 and 1..N-1medium
5. 5.Fibonacci Number
   Base 1D DP: prev2, prev1, curr variableseasy
6. 6.Decode Ways
   1D DP: dp[i] += dp[i-1] (if 1-digit valid) + dp[i-2] (if 2-digit valid)medium
7. 7.Coin Change
   Amount 1D DP: dp[a] = min(dp[a], 1 + dp[a-coin]) initialized to INFmedium
8. 8.Coin Change II
   Combination count: dp[a] += dp[a-coin] with outer coin loopmedium
9. 9.Perfect Squares
   Amount 1D DP: dp[i] = min(dp[i], 1 + dp[i - s*s])medium
10. 10.Word Break
    String suffix 1D DP: dp[i] = true if dp[j] && wordDict.contains(s[j:i])medium
11. 11.Maximum Subarray
    Kadane 1D DP: dp[i] = max(nums[i], nums[i] + dp[i-1])easy
12. 12.Maximum Product Subarray
    Track currentMax and currentMin 1D DP variablesmedium
13. 13.Longest Increasing Subsequence
    1D DP ending at i: dp[i] = 1 + max(dp[j]) for j < imedium
14. 14.Partition Equal Subset Sum
    Target sum 1D DP: right-to-left loop for target = sum/2medium
15. 15.Target Sum
    Subset sum 1D DP: convert target to positive sum P = (sum + target)/2medium
16. 16.0/1 Knapsack — Space Optimized
    Capacity 1D DP: right-to-left loop ensures single item usemedium
17. 17.Combination Sum IV
    Permutation 1D DP: outer target loop, inner coin loopmedium
18. 18.Delete and Earn
    Frequency sum transformation into House Robber 1D DPmedium
19. 19.Integer Break
    1D DP: dp[i] = max(j * (i-j), j * dp[i-j])medium
20. 20.Best Time to Buy and Sell Stock variants
    1D State variables: hold, sold, reset updated dailymedium

1. 21.Jump Game variants
   Boolean or min steps 1D DP array reachable from leftmedium
2. 22.Tribonacci Number
   3-state 1D DP: dp[i] = dp[i-1] + dp[i-2] + dp[i-3]easy
3. 23.Domino and Tromino Tiling
   Multi-state 1D DP for board coverage possibilitiesmedium
4. 24.House Robber style scheduling
   Non-adjacent interval selection 1D DPmedium
5. 25.Minimum Cost for Tickets
   Day-based 1D DP: min cost for 1-day, 7-day, 30-day passesmedium
6. 26.Number of Dice Rolls With Target Sum
   Target 1D DP: sum combination count across dicemedium
7. 27.Ugly Number II
   3-pointer 1D DP: min(dp[i2]*2, dp[i3]*3, dp[i5]*5)medium
8. 28.Longest Valid Parentheses — DP approach
   1D DP ending at i: dp[i] tracks longest valid match ending at ihard
9. 29.Maximum Sum Circular Subarray — related
   Kadane 1D DP min/max total sum subtractionmedium
10. 30.Weighted Interval Scheduling — DP + Binary Search
    1D DP on sorted end times with binary search for non-overlapping predecessorhard

1. Answer mainly depends on position i?dp[i]
2. Current answer depends on earlier positions?1D DP
3. Only previous 1–2 states needed?Space Optimization O(1)
4. State dimension is numerical (amount / sum)?1D Amount DP
5. Need max subarray sum ending at i?Kadane 1D DP

package main

import "fmt"

// Space-Optimized 1D DP for House Robber: O(N) time, O(1) space
func rob(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    prev2, prev1 := 0, 0
    for _, num := range nums {
        // Transition: current = max(skip, take)
        take := num + prev2
        skip := prev1
        current := take
        if skip > take {
            current = skip
        }
        prev2 = prev1
        prev1 = current
    }
    return prev1
}

// 1D Amount DP for Coin Change: O(Amount * Coins) time, O(Amount) space
func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    const inf = 1e9
    for i := 1; i <= amount; i++ {
        dp[i] = inf
    }
    dp[0] = 0 // Base case

    for a := 1; a <= amount; a++ {
        for _, coin := range coins {
            if a >= coin && dp[a-coin]+1 < dp[a] {
                dp[a] = dp[a-coin] + 1
            }
        }
    }
    if dp[amount] == inf {
        return -1
    }
    return dp[amount]
}

func main() {
    fmt.Println("Max Robbed:", rob([]int{2, 7, 9, 3, 1}))       // 12
    fmt.Println("Min Coins:", coinChange([]int{1, 2, 5}, 11)) // 3
}

Core 1D DP Patterns & Shapes

Define dp[i] Cell Meaning → Set Base Cases → Transition → Answer
Previous 1–2 States → Rolling variables optimize space to O(1)
0/1 Knapsack 1D Table → Capacity loop runs Right-to-Left
Unbounded Knapsack 1D Table → Capacity loop runs Left-to-Right
LIS / Subarray DP → Answer is max(dp), not always dp[last]

1D DP Variants & Space Optimization

Common Interview Mistakes

• • Coding before explicitly defining what dp[i] represents in plain language.
• • Wrong base case initializations (e.g. using 0 for minimum problems instead of INF).
• • Returning dp[N-1] when the answer is max(dp) across the array (common mistake in LIS and Kadane).
• • Running 0/1 Knapsack 1D capacity loop left-to-right (accidentally allowing item reuse).
• • Assuming all 1D DP solutions run in O(N) time (LIS is O(N²) because each state scans all j < i).
• • Optimizing space to O(1) prematurely before validating the full array transition logic.
• • Confusing array index state (dp[i]) with numerical amount state (dp[amount]).
• • Failing to handle negative numbers in Maximum Product Subarray (requires currentMax and currentMin).

Interview Rules

Single parameter defines subproblem → 1D DP
Rule 1                              → Define dp[i] meaning explicitly
Rule 2                              → Set base cases
Rule 3                              → Identify previous state window (1 state, 2 states, or all j < i)
Rule 4                              → 0/1 Knapsack 1D = Capacity loop Right-to-Left
Rule 5                              → Unbounded Knapsack 1D = Capacity loop Left-to-Right
Rule 6                              → Window of size 1–2? → Rolling variables for O(1) space
Time Complexity                     → States × Work per State
Space Complexity                    → O(N) Array or O(1) Rolling Variables

💡 Golden Rule: If one variable completely describes the subproblem, store the answer in one DP dimension and build each state from already-solved states.

1D DP State: dp[i] or dp[amount]
Golden Steps: Define Cell → Base Cases → Transition → Fill → Answer
0/1 Knapsack 1D: Loop capacity Right-to-Left
Unbounded 1D: Loop capacity Left-to-Right
LIS & Kadane: dp[i] means "ending at i"; final answer is max(dp)
Rolling variables (prev2, prev1) achieve O(1) memory