Pattern 1a: Simple Accumulation

Core Concept: Build answer at position i by simply accumulating results from previous positions without complex constraints.

---

The Pattern

THE MENTAL MODEL

Think of a simple chain reaction:

1. Start with base case values
2. At each position, add or combine results from 1-2 steps back
3. No skip constraints, no complex conditions
4. Pure accumulation: dp[i] = f(dp[i-1], dp[i-2])

This is the simplest linear sequence pattern.

Pattern Recognition

WHEN YOU SEE THIS PATTERN

Keywords: "how many ways", "count paths", "fibonacci-like", "accumulate"

Structure:

• Decision at each step is straightforward
• No adjacency constraints (unlike House Robber)
• Simple addition of previous states
• Classic recursive accumulation

State: dp[i] = count/sum of ways to reach position i

Transition: dp[i] = dp[i-1] + dp[i-2] (or similar simple combination)

---

Problems in This Category

Core Problems

1. Fibonacci Number - The foundation pattern
2. Climbing Stairs - Direct Fibonacci application
3. Min Cost Climbing Stairs - Fibonacci with minimization
4. Decode Ways - Conditional Fibonacci (with validity checks)

Common Thread

All these problems share:

• ✅ Simple accumulation from previous states
• ✅ Looking back 1-2 positions
• ✅ No "skip" constraints (you CAN use adjacent values)
• ✅ Pure addition or simple min/max operations

---

Key Differences from Other Categories

DON'T CONFUSE WITH

vs. Pattern 1b (Selection with Skip Constraint):

• 1a: Can use BOTH dp[i-1] AND dp[i-2] freely
• 1b: If you take i, you CANNOT use i-1 (House Robber pattern)

Example:

• Climbing Stairs (1a): dp[i] = dp[i-1] + dp[i-2] ✓ (sum both)
• House Robber (1b): dp[i] = max(dp[i-1], dp[i-2] + nums[i]) (choose one)

---

Template Code

public int simpleAccumulation(int n) {
    // Base cases
    if (n <= 1) return base_value;

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

    // Simple accumulation
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];  // Or other simple combination
    }

    return dp[n];
}

Space-Optimized Version:

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

    int prev2 = base_case_0;
    int prev1 = base_case_1;

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

    return prev1;
}

---

Learning Path

MASTER THIS FIRST

This is the foundation of linear sequence DP. Master these before moving to more complex patterns:

Week 1: Fibonacci, Climbing Stairs Week 2: Min Cost Climbing Stairs Week 3: Decode Ways (adds conditional logic)

Once you can solve these effortlessly, you're ready for Pattern 1b (Skip Constraints) and Pattern 1c (Subarrays).