Pattern 1: Linear Sequence Decision Problems

The Foundation Pattern: Walk left-to-right, at each position look backward and make a decision based on previous positions.

---

The Core Pattern

THE MENTAL MODEL

Imagine walking along a path with numbered stones. At each stone:

1. You look backward at previous stones
2. You make a decision based on what you found
3. You record your answer at the current stone
4. You continue to the next stone

This is Linear Sequence DP.

Pattern Recognition

WHEN YOU SEE THIS PATTERN

Keywords: "at each position", "sequence", "array", "previous", "up to index i"

Structure:

• Single array/sequence to process
• Decision at each position affects future
• Need to track "best answer up to position i"

State: dp[i] represents "best answer up to/ending at position i"

Transition: Look backward at dp[i-1], dp[i-2], or dp[j] where j < i

---

Category 1: Core Pattern Problems

1. Climbing Stairs (LC 70)

PROBLEM

You're climbing a staircase. It takes n steps to reach the top. Each time you can climb 1 or 2 steps. How many distinct ways can you climb to the top?

State Definition: dp[i] = number of ways to reach step i

Transition: dp[i] = dp[i-1] + dp[i-2]

• From step i-1, take 1 step
• From step i-2, take 2 steps

public int climbStairs(int n) {
    if (n <= 2) return n;

    int[] dp = new int[n + 1];
    dp[0] = 1;  // 1 way to stay at ground
    dp[1] = 1;  // 1 way to reach step 1

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    return dp[n];
}

Pure Recursion

public int climbStairs(int n) {
    // Base cases
    if (n == 0) {
        return 1;  // 1 way to stay at ground
    }

    if (n == 1) {
        return 1;  // 1 way to reach step 1
    }

    if (n == 2) {
        return 2;  // 2 ways to reach step 2
    }

    // Recursive case

    // First option: come from step (n-1) and take 1 step
    int waysFromPreviousStep = climbStairs(n - 1);

    // Second option: come from step (n-2) and take 2 steps
    int waysFromTwoStepsBack = climbStairs(n - 2);

    // Total ways = sum of both options
    int totalWays = waysFromPreviousStep + waysFromTwoStepsBack;

    return totalWays;
}

Recursion with Memoization

public int climbStairs(int n) {
    int[] memo = new int[n + 1];
    return func(n, memo);
}

private int func(int n, int[] memo) {
    // Base cases
    if (n <= 2) return n;

    // Already calculated?
    if (memo[n] != 0) return memo[n];

    // Calculate recursively
    int fromOneStep = func(n - 1, memo);
    int fromTwoSteps = func(n - 2, memo);
    int totalWays = fromOneStep + fromTwoSteps;

    // Store and return
    memo[n] = totalWays;
    return totalWays;
}

The Memoization Hook

We transfer another information. It is like a hook outside of the world you are in and it registers information and you can reach it across different stack frames.

The memo array lives outside the recursive call stack. Each recursive call can read and write to it, creating a shared memory that persists across all function calls. This breaks the isolation of pure recursion and allows different parts of the recursion tree to communicate.

---

2. House Robber (LC 198)

PROBLEM

You are a robber planning to rob houses along a street. Each house has a certain amount of money. Adjacent houses have security systems—you cannot rob two adjacent houses. Return the maximum amount you can rob.

State Definition: dp[i] = maximum money you can rob from houses 0 to i

Transition: dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])

• Don't rob house i: take dp[i-1]
• Rob house i: take dp[i-2] + nums[i] (can't use i-1)

public int rob(int[] nums) {
    if (nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];

    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);

    for (int i = 2; i < nums.length; i++) {
        dp[i] = Math.max(
            dp[i-1],              // don't rob house i
            dp[i-2] + nums[i]     // rob house i
        );
    }

    return dp[nums.length - 1];
}

---

3. Min Cost Climbing Stairs (LC 746)

State Definition: dp[i] = minimum cost to reach position i

Transition: dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int[] dp = new int[n + 1];

    dp[0] = 0;  // Reach step 0 for free
    dp[1] = 0;  // Reach step 1 for free

    for (int i = 2; i <= n; i++) {
        dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
    }

    return dp[n];  // Cost to reach the top
}

Another Approach

State Definition: dp[i] = minimum cost to reach step i and pay cost[i]

Transition: dp[i] = Math.min(dp[i-1], dp[i-2]) + cost[i]

public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int[] dp = new int[n];
    dp[0] = cost[0];
    dp[1] = cost[1];

    for (int i = 2; i < n; i++) {
        dp[i] = Math.min(dp[i-1], dp[i-2]) + cost[i];
    }

    // Can start from step 0 or 1
    return Math.min(dp[n-1], dp[n-2]);
}

---

4. Decode Ways (LC 91)

Problem Statement

A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

• "AAJF" with the grouping (1 1 10 6)
• "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

Example 1:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:

Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").

Constraints:

• 1 <= s.length <= 100
• s contains only digits and may contain leading zero(s).

State Definition: dp[i] = number of ways to decode string up to index i

Transition:

• Single digit decode: dp[i] += dp[i-1] (if valid)
• Two digit decode: dp[i] += dp[i-2] (if valid)

public int numDecodings(String s) {
    if (s.charAt(0) == '0') return 0;

    int n = s.length();
    int[] dp = new int[n + 1];
    dp[0] = 1;  // empty string
    dp[1] = 1;  // first character

    for (int i = 2; i <= n; i++) {
        // Single digit
        int oneDigit = Integer.parseInt(s.substring(i-1, i));
        if (oneDigit >= 1 && oneDigit <= 9) {
            dp[i] += dp[i-1];
        }

        // Two digits
        int twoDigits = Integer.parseInt(s.substring(i-2, i));
        if (twoDigits >= 10 && twoDigits <= 26) {
            dp[i] += dp[i-2];
        }
    }

    return dp[n];
}

---

5. Fibonacci Number (LC 509)

State Definition: dp[i] = Fibonacci number at position i

Transition: dp[i] = dp[i-1] + dp[i-2]

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

    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    return dp[n];
}

---

Category 2: Single Choice at Each Position

6. Delete and Earn (LC 740)

State Definition: dp[i] = maximum points you can earn up to number i

Transition: dp[i] = Math.max(dp[i-1], dp[i-2] + points[i])

Pattern Recognition: This is actually House Robber in disguise! If you take number i, you can't take i-1 or i+1.

---

7. House Robber II (LC 213) - Circular

State Definition: dp[i] = maximum money from houses in linear subarray

Transition: Same as House Robber, but run twice:

• Case 1: Rob houses 0 to n-2 (exclude last)
• Case 2: Rob houses 1 to n-1 (exclude first)

Why? In a circle, you can't rob both first and last house.

---

8. Maximum Alternating Subsequence Sum (LC 1911)

State Definition: dp[i] = maximum alternating sum ending at position i

Transition: Look back at previous positions with opposite sign

---

9. Best Time to Buy and Sell Stock (LC 121)

State Definition: dp[i] = maximum profit up to day i

Transition: dp[i] = Math.max(dp[i-1], prices[i] - minPrice)

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int maxProfit = 0;

    for (int i = 0; i < prices.length; i++) {
        minPrice = Math.min(minPrice, prices[i]);
        maxProfit = Math.max(maxProfit, prices[i] - minPrice);
    }

    return maxProfit;
}

---

10. Maximum Subarray (LC 53) - Kadane's Algorithm

State Definition: dp[i] = maximum sum of subarray ending at position i

Transition: dp[i] = Math.max(dp[i-1] + nums[i], nums[i])

public int maxSubArray(int[] nums) {
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int maxSum = dp[0];

    for (int i = 1; i < nums.length; i++) {
        // Either extend previous subarray or start fresh
        dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
        maxSum = Math.max(maxSum, dp[i]);
    }

    return maxSum;
}

KADANE'S ALGORITHM

This is one of the most elegant DP patterns. The key insight:

At each position, either extend the previous subarray or start a new one.

---

Category 3: Constrained Choices

11. Maximum Sum Circular Subarray (LC 918)

State Definition: dp[i] = max/min sum ending at position i

Transition: Apply Kadane's pattern twice (for max and min)

Circular Array Trick:

• Case 1: Maximum subarray is in the middle (use Kadane's)
• Case 2: Maximum subarray wraps around (total - minimum subarray)

---

12. Longest Increasing Subsequence (LC 300)

State Definition: dp[i] = length of longest increasing subsequence ending at i

Transition: dp[i] = Math.max(dp[j] + 1) for all j < i where nums[j] < nums[i]

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);  // Each element is a subsequence of length 1

    int maxLen = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }

    return maxLen;
}

COMPLEXITY NOTE

This solution is O(n²). There's an O(n log n) solution using binary search + patience sorting.

---

13. Wiggle Subsequence (LC 376)

State Definition: dp[i] = length of longest wiggle subsequence ending at i

Transition: Look back at previous positions with opposite trend (up/down)

---

14. Paint House (LC 256)

State Definition: dp[i][color] = minimum cost to paint houses 0 to i with house i being color

Transition: dp[i][c] = Math.min(dp[i-1][other colors]) + cost[i][c]

public int minCost(int[][] costs) {
    int n = costs.length;
    int[][] dp = new int[n][3];

    dp[0][0] = costs[0][0];
    dp[0][1] = costs[0][1];
    dp[0][2] = costs[0][2];

    for (int i = 1; i < n; i++) {
        dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + costs[i][0];
        dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + costs[i][1];
        dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + costs[i][2];
    }

    return Math.min(dp[n-1][0], Math.min(dp[n-1][1], dp[n-1][2]));
}

---

15. Paint Fence (LC 276)

State Definition: dp[i] = number of ways to paint fence up to post i

Transition: dp[i] = dp[i-1] * (k-1) + dp[i-2] * (k-1)

---

Category 4: Multiple States per Position

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

State Definition:

• hold[i] = max profit on day i if holding stock
• sold[i] = max profit on day i if just sold
• rest[i] = max profit on day i if resting

Transition:

• hold[i] = Math.max(hold[i-1], rest[i-1] - prices[i])
• sold[i] = hold[i-1] + prices[i]
• rest[i] = Math.max(rest[i-1], sold[i-1])

---

17. Best Time to Buy and Sell Stock II (LC 122)

State Definition: dp[i] = maximum profit up to day i (unlimited transactions)

Transition: dp[i] = dp[i-1] + Math.max(0, prices[i] - prices[i-1])

Greedy Insight: Capture every upward price movement!

---

18. Maximum Product Subarray (LC 152)

State Definition:

• maxDP[i] = maximum product ending at i
• minDP[i] = minimum product ending at i (for handling negatives)

Transition:

maxDP[i] = Math.max(nums[i], Math.max(maxDP[i-1] * nums[i], minDP[i-1] * nums[i]));
minDP[i] = Math.min(nums[i], Math.min(maxDP[i-1] * nums[i], minDP[i-1] * nums[i]));

WHY TRACK BOTH MAX AND MIN?

A negative number can flip the smallest product into the largest!

Example: [-2, 3, -4]

• At -4: minDP[-2] * (-4) becomes the maximum!

---

19. Word Break (LC 139)

State Definition: dp[i] = true if string s[0...i-1] can be segmented

Transition: Check if dp[j] is true AND s[j...i-1] is in dictionary, for all j < i

public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;  // empty string

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[n];
}

---

20. Domino and Tromino Tiling (LC 790)

State Definition: dp[i] = number of ways to tile a 2 × i board

Transition: dp[i] = dp[i-1] + dp[i-2] + 2 * dp[i-3]

Why this formula? Consider how the last piece can be placed:

• Vertical domino: dp[i-1]
• Horizontal domino pair: dp[i-2]
• Tromino patterns: 2 * dp[i-3]

---

The Common Thread

WHAT MAKES THESE ALL THE SAME PATTERN?

Every problem has:

1. Single index i moving left-to-right
2. State dp[i] represents "best answer up to/ending at position i"
3. Transition looks backward at dp[i-1], dp[i-2], or dp[j] where j < i
4. No 2D grid, no intervals, no subsequence pairs—just linear progression

---

Pattern Recognition Checklist

USE THIS CHECKLIST

When you see a new problem, ask:

• Is it a single array/sequence?
• Do I need to make decisions at each position?
• Does the decision at position i depend on previous positions?
• Can I define dp[i] as "best answer up to/ending at i"?
• Can I build dp[i] from dp[i-1], dp[i-2], or earlier states?

If all YES → Pattern 1: Linear Sequence Decision

---

Common Mistakes

COMMON PITFALLS

Mistake 1: Confusing "up to i" vs "ending at i"

House Robber: dp[i] = max money from houses 0 to i Maximum Subarray: dp[i] = max sum ending at i

Why it matters:

• "up to i" = cumulative answer
• "ending at i" = must include element i

---

Mistake 2: Forgetting base cases

Always initialize:

• dp[0] - what's the answer for the first element?
• dp[1] - what about the second element (if you look back 2 positions)?

---

Mistake 3: Off-by-one errors

When looking back at dp[i-2], make sure i >= 2!

// WRONG
dp[i] = dp[i-2] + nums[i];  // What if i = 1?

// RIGHT
if (i >= 2) {
    dp[i] = dp[i-2] + nums[i];
}

---

Space Optimization

REDUCING SPACE COMPLEXITY

Most linear sequence DP only needs O(1) space!

Why? If you only look back at dp[i-1] and dp[i-2], you only need 2 variables.

Example (Fibonacci):

// O(n) space
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
}

// O(1) space
int prev2 = 0, prev1 = 1;
for (int i = 2; i <= n; i++) {
    int curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
}

---

Learning Path

RECOMMENDED ORDER

Week 1: Core Foundation (Problems 1-5)

• Master the "look back 1-2 steps" pattern
• Understand base cases

Week 2: Variations (Problems 6-10)

• Learn to recognize disguised patterns
• Practice Kadane's algorithm

Week 3: Constraints (Problems 11-15)

• Handle multiple constraints
• Practice with colors/states

Week 4: Advanced States (Problems 16-20)

• Multiple states per position
• Complex transitions

Total: 20 problems × 4 weeks = Pattern 1 mastery

---

Final Thoughts

THIS IS YOUR FOUNDATION

Pattern 1: Linear Sequence Decision is the most common DP pattern.

Master these 20 problems, and you'll:

• Recognize this structure instantly in new problems
• Know how to define dp[i] intuitively
• Understand when to use "up to i" vs "ending at i"
• See connections between seemingly different problems

This is your DP foundation. Build it strong.

---

Quick Reference Table

Problem	State	Look Back	Pattern Variant
Climbing Stairs	ways to reach i	i-1, i-2	Classic Fibonacci
House Robber	max money to i	i-1, i-2	Binary choice
Min Cost Stairs	min cost to i	i-1, i-2	Minimization
Decode Ways	ways to decode to i	i-1, i-2	Conditional sum
Max Subarray	max sum ending at i	i-1	Kadane's
LIS	length ending at i	all j < i	O(n²) scan
Paint House	min cost with color	i-1 (other colors)	Multi-state
Word Break	can break to i	all j < i	Substring check

---

Next Steps

AFTER MASTERING PATTERN 1

You're ready for:

• Pattern 2: Grid Traversal (2D progression)
• Pattern 3: Bounded Knapsack (resource constraints)
• Pattern 5: State Machine (transitions between states)

But first: Make sure you can solve any of these 20 problems with confidence and without looking at the solution.