1d Dp Problems - Learning Module

Loading content...

0/279

State: Single Index — The Unifying Framework

The Heart of 1D Dynamic Programming

We've now studied three foundational 1D DP problems: Fibonacci, Climbing Stairs, and House Robber. While they differ in context and details, they share a profound structural similarity: the entire problem state is captured by a single integer index.

This isn't coincidental — it's the defining characteristic of 1D DP. In this page, we'll abstract away from specific problems to understand the general framework that makes 1D DP so powerful and widely applicable.

The Single-Index Insight:

In 1D DP, the state can be expressed as dp[i] where i is a single integer. The value dp[i] might represent counts, optimal values, boolean reachability, or other quantities — but the state itself is always a single position along some linear dimension.

What You Will Learn

By the end of this page, you will: (1) Understand what makes a problem '1D' in DP terms, (2) Master state definition for various problem types, (3) Recognize common 1D DP recurrence patterns, (4) Identify space optimization opportunities, (5) Transform unfamiliar problems into 1D DP form, (6) Know when 1D DP is insufficient and higher dimensions are needed.

What is 'State' in Dynamic Programming?

State is the most critical concept in DP. It's what distinguishes DP from brute force and determines the efficiency of your solution.

Formal Definition:

A state in DP is a complete description of a subproblem that contains all information needed to compute the optimal solution from that point forward.

Key Properties of Good State Design:

Sufficient Information: The state must contain everything needed to solve the subproblem. If you need to know additional context that isn't in the state, your state is incomplete.
No Redundant Information: The state should be minimal — don't track information that doesn't affect the solution. Redundant state variables increase DP table size and hurt performance.
Finite and Enumerable: The state space must be finite so we can build a DP table. Continuous or infinite state spaces require different techniques.
Computable Transitions: Given the state, we must be able to compute transitions to/from other states.

State Comparison Across 1D DP Problems
Problem	State: dp[i] represents	What i indexes	State Space Size
Fibonacci	The i-th Fibonacci number	Sequence position	n + 1
Climbing Stairs	Ways to reach step i	Stair number	n + 1
House Robber	Max money from houses 0..i	House index	n
Coin Change (min)	Min coins to make amount i	Amount value	amount + 1
Longest Increasing Subseq	LIS ending at index i	Array index	n

The State Definition Question

When designing DP, always ask: 'What do I need to know to solve the problem from this point forward?' The answer is your state. If the answer is 'just the position i,' you have 1D DP. If you need more (like remaining capacity, or previous choices), you may need 2D or higher.

Types of 1D DP Problems

1D DP problems fall into several categories based on what the dp[i] value represents and how transitions work:

Category 1: Counting Problems

•Question: How many ways to reach state i?
•Recurrence: dp[i] = Σ dp[predecessor states]
•Examples: Climbing Stairs (ways to reach step), Decode Ways, Unique Paths
•Base Case: Usually dp[0] = 1 (one way to be at the start)

Category 2: Optimization Problems

•Question: What is the min/max value achievable at state i?
•Recurrence: dp[i] = min/max(dp[predecessor] + cost/value)
•Examples: House Robber (max money), Coin Change (min coins), Min Cost Climbing Stairs
•Base Case: Depends on optimization direction (0 for max, 0 or ∞ for min)

Category 3: Decision Problems

•Question: Is it possible to reach state i?
•Recurrence: dp[i] = dp[i] OR dp[predecessor states]
•Examples: Jump Game (can reach end?), Word Break (can segment string?)
•Base Case: dp[0] = true (start is reachable)

Category 4: Sequence Problems

•Question: What is the optimal subsequence property ending at i?
•Recurrence: dp[i] = best(dp[j] for j < i where condition holds) + contribution[i]
•Examples: Longest Increasing Subsequence, Maximum Subarray Sum
•Base Case: dp[i] = base value for starting a new sequence at i

The Operator Determines the Type

Counting uses SUM. Optimization uses MIN or MAX. Decision uses OR. Recognizing which type applies immediately narrows down the recurrence structure.

Common 1D DP Recurrence Patterns

Most 1D DP recurrences fall into a few common patterns. Recognizing these accelerates problem-solving:

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
/**
 * Pattern: dp[i] depends on a fixed number of previous states
 * 
 * Recurrence: dp[i] = f(dp[i-1], dp[i-2], ..., dp[i-k]) for constant k
 * 
 * Space: Can always reduce to O(k) by keeping only last k values
 * 
 * Examples:
 * - Fibonacci: dp[i] = dp[i-1] + dp[i-2]  (k=2)
 * - Tribonacci: dp[i] = dp[i-1] + dp[i-2] + dp[i-3]  (k=3)
 * - House Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i])  (k=2)
 * - Min Cost Climbing: dp[i] = min(dp[i-1], dp[i-2]) + cost[i]  (k=2)
 */
 
// Generic template for fixed lookback (k=2)
function fixedLookbackTemplate(n: number, computeNext: (prev1: number, prev2: number, i: number) => number): number {
    if (n <= 1) return n;  // Adjust base cases as needed
    
    let prev2 = 0;  // dp[i-2]
    let prev1 = 1;  // dp[i-1]
    
    for (let i = 2; i <= n; i++) {
        const current = computeNext(prev1, prev2, i);
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}
 
// Example: Tribonacci
const tribonacci = (n: number): number => {
    if (n === 0) return 0;
    if (n <= 2) return 1;
    
    let prev3 = 0, prev2 = 1, prev1 = 1;
    
    for (let i = 3; i <= n; i++) {
        const current = prev1 + prev2 + prev3;
        prev3 = prev2;
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
};

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
/**
 * Pattern: dp[i] depends on ALL previous states
 * 
 * Recurrence: dp[i] = aggregate(dp[j] for j in 0..i-1 where condition(j,i))
 * 
 * Time: Usually O(n²) since each state looks at all predecessors
 * Space: O(n), cannot reduce further (need all previous values)
 * 
 * Examples:
 * - Longest Increasing Subsequence: dp[i] = max(dp[j] for j<i if arr[j]<arr[i]) + 1
 * - Jump Game II: dp[i] = min(dp[j] for j<i if j + arr[j] >= i) + 1
 * - Word Break: dp[i] = OR(dp[j] for j<i if substring[j..i] is in dict)
 */
 
function longestIncreasingSubsequence(nums: number[]): number {
    const n = nums.length;
    if (n === 0) return 0;
    
    // dp[i] = length of LIS ending at index i
    const dp: number[] = new Array(n).fill(1);  // Each element is LIS of length 1
    
    for (let i = 1; i < n; i++) {
        // Look back at ALL previous indices
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {  // Can extend LIS ending at j
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    
    return Math.max(...dp);  // LIS might end at any position
}
 
// Note: LIS can be optimized to O(n log n) with binary search, 
// but the O(n²) DP is the foundation to understand 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Pattern: dp[i] incorporates all previous elements via aggregation
 * 
 * Recurrence: dp[i] = best(dp[i-1] + contribution[i], fresh start)
 * 
 * Time: O(n), each state computed in O(1)
 * Space: O(1) if we only need the global aggregate
 * 
 * Examples:
 * - Maximum Subarray (Kadane's): dp[i] = max(dp[i-1] + nums[i], nums[i])
 * - Best Time to Buy/Sell Stock: track min so far, max profit
 */
 
function maxSubarrayKadane(nums: number[]): number {
    if (nums.length === 0) return 0;
    
    let currentMax = nums[0];  // Max subarray ending at current position
    let globalMax = nums[0];   // Max subarray seen so far
    
    for (let i = 1; i < nums.length; i++) {
        // Either extend the previous subarray or start fresh from here
        currentMax = Math.max(currentMax + nums[i], nums[i]);
        globalMax = Math.max(globalMax, currentMax);
    }
    
    return globalMax;
}
 
function maxProfit(prices: number[]): number {
    if (prices.length === 0) return 0;
    
    let minPriceSoFar = prices[0];
    let maxProfit = 0;
    
    for (let i = 1; i < prices.length; i++) {
        // Can we profit by selling today?
        maxProfit = Math.max(maxProfit, prices[i] - minPriceSoFar);
        // Update the minimum price seen
        minPriceSoFar = Math.min(minPriceSoFar, prices[i]);
    }
    
    return maxProfit;
}

Pattern Recognition Speeds Solution

When you see a new 1D DP problem, immediately ask: Is it fixed lookback? Is it all-previous lookback? Is it prefix aggregation? The pattern determines time complexity and space optimization potential.

Visualizing State Transitions

Understanding DP becomes clearer when we visualize states as nodes in a graph and transitions as directed edges. Let's see how our studied problems look as state transition diagrams.

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
FIBONACCI / CLIMBING STAIRS (n=6)
State Space: [0, 1, 2, 3, 4, 5, 6]
 
Transitions (who flows into i):
[0] ──┬──→ [1] ──┬──→ [2] ──┬──→ [3] ──┬──→ [4] ──┬──→ [5] ──┬──→ [6]
      │         │         │         │         │         │
      └─────────┘         └─────────┘         └─────────┘
      i-1 → i             i-1 → i             i-1 → i
      i-2 → i             i-2 → i             i-2 → i
 
dp[i] = dp[i-1] + dp[i-2] (sum incoming edges)
 
---
 
HOUSE ROBBER (nums = [2, 7, 9, 3, 1])
States: [0, 1, 2, 3, 4] representing houses
 
Two choice types per state:
  - SKIP: Take dp[i-1] (no constraint)
  - ROB: Take dp[i-2] + nums[i] (must skip i-1)
 
Transition visualization:
[0] ──┬──→ [1] ──┬──→ [2] ──┬──→ [3] ──┬──→ [4]
      │         │         │         │         
      └─────────┴─────────┴─────────┴─────────...
               (skip paths: i-1 → i)
      └─────────────┬─────────────┬─────────...
                    (rob paths: i-2 → i, skipping i-1)
 
dp[i] = max(incoming paths)
 
---
 
LONGEST INCREASING SUBSEQUENCE (nums = [10, 9, 2, 5, 3, 7, 101, 18])
States: [0, 1, 2, 3, 4, 5, 6, 7] representing ending positions
 
Transitions: ALL j < i where nums[j] < nums[i]
 
  [0]   [1]   [2]   [3]   [4]   [5]   [6]   [7]
  10     9     2     5     3     7    101    18
                     ↑     ↑     ↑     ↑      ↑
                 from 2  from 2  from 2,3,5  from many...
                         from 3  from 5,7
 
dp[5]=3 (2→5→7), dp[6]=4 (2→3→7→101 or 2→5→7→101), dp[7]=4

The DAG Property:

All valid DP problems have an important property: the state transition graph is a Directed Acyclic Graph (DAG). This is what makes DP work — we can process states in topological order, ensuring all predecessors are computed before each state.

In 1D DP with forward dependencies (dp[i] depends on smaller indices), the natural left-to-right order is a valid topological order. This is why simple for loops work.

Cycles Mean Infinite Loops

If your state transitions form a cycle, DP doesn't directly apply. You'd need different techniques (like iterative refinement, graph algorithms, or reformulating the problem). Always verify your dependencies are acyclic.

Space Optimization Principles

A key advantage of understanding 1D DP structure is recognizing space optimization opportunities. The principle is simple:

If dp[i] only depends on a fixed window of previous values, store only that window.

Space Optimization Based on Lookback
Lookback Pattern	Naive Space	Optimized Space	Example Problems
dp[i-1] only	O(n)	O(1) — 1 variable	Running sum, Simple running max
dp[i-1], dp[i-2]	O(n)	O(1) — 2 variables	Fibonacci, Climbing Stairs, House Robber
dp[i-1], ..., dp[i-k] (fixed k)	O(n)	O(k) — circular buffer	Tribonacci, K-Step Climbing
All previous dp[j] for j < i	O(n)	O(n) — no reduction	LIS, Word Break
dp[i-1] but need path	O(n)	O(n) — store path	Path reconstruction needed

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
/**
 * Space Optimization with Modular Indexing (Rolling Array)
 * 
 * When lookback is k states, use an array of size k with modular access.
 * dp[i] is stored at position i % k.
 * 
 * This technique is essential for DP problems with fixed lookback.
 */
 
// Example: K-Step Climbing Stairs with O(k) space
function climbStairsKRolling(n: number, k: number): number {
    if (n === 0) return 1;
    if (k <= 0) return 0;
    
    // Rolling array of size k
    const dp: number[] = new Array(k).fill(0);
    dp[0] = 1;  // dp[0] = 1
    
    for (let i = 1; i <= n; i++) {
        // dp[i] = sum of dp[i-1] + dp[i-2] + ... + dp[i-k]
        // But we only store last k values in rolling array
        
        // Clear the value at position i % k (it was dp[i-k], now will be dp[i])
        let sum = 0;
        for (let j = 1; j <= Math.min(k, i); j++) {
            sum += dp[(i - j + k) % k];  // Access dp[i-j] via modular index
        }
        dp[i % k] = sum;
    }
    
    return dp[n % k];
}
 
// Example: General template for fixed lookback k
function rollingDPTemplate<T>(
    n: number,
    k: number,
    initialValues: T[],
    computeNext: (getDP: (offset: number) => T, i: number) => T
): T {
    const dp: T[] = [...initialValues];
    
    // Ensure dp has size k
    while (dp.length < k) {
        dp.push(undefined as T);
    }
    
    for (let i = initialValues.length; i <= n; i++) {
        // getDP(offset) returns dp[i - offset] from the rolling array
        const getDP = (offset: number): T => dp[(i - offset + k) % k];
        dp[i % k] = computeNext(getDP, i);
    }
    
    return dp[n % k];
}
 
// Fibonacci using template
const fibWithTemplate = (n: number): number => 
    rollingDPTemplate<number>(n, 2, [0, 1], (getDP, i) => getDP(1) + getDP(2));

Trade-off: Space vs Features

Space optimization sacrifices the ability to reconstruct the full DP table afterward. If you need path reconstruction or to query arbitrary dp[i], you must keep the full O(n) table. Decide based on problem requirements.

Debugging 1D DP Solutions

DP bugs can be subtle and frustrating. Here's a systematic approach to debugging 1D DP solutions:

Common 1D DP Bugs and Fixes

•Off-by-one errors in base cases: Carefully verify dp[0] and dp[1]. Trace through a tiny example (n=2) by hand.
•Wrong loop bounds: Check if loop should be i <= n or i < n. Match the array indexing convention.
•Incorrect recurrence formula: Write out the recurrence mathematically before coding. Verify each term.
•Initialization errors: For min problems, initialize to Infinity (not 0). For counting, ensure dp[0] = 1 not 0.
•Space optimization broke something: Test with O(n) space first, then carefully optimize while checking against the full table.
•Integer overflow: For counting problems, values grow exponentially. Use BigInt or take modulo.
•Edge cases missed: Test empty input, single element, two elements, and inputs that hit boundary conditions.

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
/**
 * DP Debugging Helper
 * 
 * Prints the full DP table for verification.
 * Use this during development, remove in production.
 */
function dpDebug<T>(
    problemName: string,
    n: number,
    dp: T[],
    input?: any
): void {
    console.log(`
=== ${problemName} Debug ===`);
    if (input) console.log("Input:", JSON.stringify(input));
    
    console.log("DP Table:");
    for (let i = 0; i < dp.length; i++) {
        console.log(`  dp[${i}] = ${dp[i]}`);
    }
    console.log(`Answer (dp[${n}]): ${dp[n]}`);
}
 
// Example usage in Climbing Stairs
function climbStairsDebug(n: number): number {
    const dp: number[] = new Array(n + 1);
    dp[0] = 1;
    dp[1] = 1;
    
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    dpDebug("Climbing Stairs", n, dp);
    return dp[n];
}
 
// Test with small input
climbStairsDebug(5);
// Output:
// === Climbing Stairs Debug ===
// DP Table:
//   dp[0] = 1
//   dp[1] = 1
//   dp[2] = 2
//   dp[3] = 3
//   dp[4] = 5
//   dp[5] = 8
// Answer (dp[5]): 8

The Hand-Trace Method

Before running code, trace through dp[0], dp[1], dp[2] by hand on paper. Verify each step matches your mental model. This catches 90% of bugs before they become frustrating debugging sessions.

When 1D DP Isn't Enough

Not all DP problems can be solved with a single index. Here's how to recognize when you need more:

Signs you need 2D or higher DP:

Two independent choices: If you're iterating over two arrays/strings simultaneously (e.g., Longest Common Subsequence), you need dp[i][j].
Capacity constraints: If there's a 'budget' that depletes (e.g., Knapsack capacity), add a dimension for remaining capacity.
State includes 'mode': If behavior changes based on context (e.g., cooldown periods), add a dimension for the mode.
History matters: If the optimal choice depends on what you did k steps ago (not just best value), you may need additional dimensions.

1D vs Higher-Dimensional DP Examples
Problem	Dimensions	State Representation	Why This Dimensionality?
Fibonacci	1D	dp[i] = F(i)	Only need sequence index
Climbing Stairs	1D	dp[i] = ways to step i	Only need position
0/1 Knapsack	2D	dp[i][w] = value with items 0..i, capacity w	Need item index AND remaining capacity
Longest Common Subseq	2D	dp[i][j] = LCS of s1[0..i], s2[0..j]	Position in BOTH strings
Edit Distance	2D	dp[i][j] = edits to transform s1[0..i] to s2[0..j]	Position in both strings
Stock Trading k transactions	3D	dp[i][j][holding] = profit at day i, j transactions, holding/not	Day, transactions used, hold status

The Dimensional Hierarchy:

0D DP: Just a single value (trivial problems with no substructure)
1D DP: Single index — O(n) states
2D DP: Two indices — O(n²) or O(n×m) states
3D DP: Three indices — O(n³) or O(n×m×k) states
Higher: Rare in practice, usually indicates a need for state compression or different techniques

As dimensions increase, both time and space grow exponentially. 1D DP is precious because it's efficient. Always try to reduce to 1D if possible.

Look for Separability

Sometimes a seemingly 2D problem can be decomposed into independent 1D problems. For example, grid problems with row-wise independence can be solved row by row. Always look for structure that simplifies dimensionality.

Practice Problem Analysis — Recognizing 1D DP

Let's analyze several problems to practice recognizing 1D DP structure:

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
/**
 * Decode Ways (LeetCode 91)
 * 
 * A message containing letters A-Z is encoded to numbers 1-26.
 * Given an encoded string of digits, count ways to decode it.
 * 
 * Example: "12" → "AB" (1,2) or "L" (12) → 2 ways
 * 
 * ANALYSIS:
 * - State: dp[i] = number of ways to decode s[0..i-1]
 * - This is 1D because we only need position in the string
 * - Recurrence: 
 *   - If s[i-1] is valid (1-9), add dp[i-1]
 *   - If s[i-2..i-1] is valid (10-26), add dp[i-2]
 * - Pattern: Fixed lookback (k=2), like Fibonacci!
 */
function numDecodings(s: string): number {
    const n = s.length;
    if (n === 0 || s[0] === '0') return 0;
    
    // dp[i] = ways to decode first i characters
    let prev2 = 1;  // dp[0]: empty string has 1 way (base case)
    let prev1 = 1;  // dp[1]: first char has 1 way if not '0'
    
    for (let i = 2; i <= n; i++) {
        let current = 0;
        
        // Single digit decode: s[i-1] (1-indexed in the dp sense)
        const oneDigit = parseInt(s[i - 1]);
        if (oneDigit >= 1 && oneDigit <= 9) {
            current += prev1;
        }
        
        // Two digit decode: s[i-2..i-1]
        const twoDigit = parseInt(s.substring(i - 2, i));
        if (twoDigit >= 10 && twoDigit <= 26) {
            current += prev2;
        }
        
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}
 
console.log(numDecodings("12"));   // 2: "AB", "L"
console.log(numDecodings("226"));  // 3: "BZ", "VF", "BBF"
console.log(numDecodings("06"));   // 0: Leading zero invalid

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
/**
 * Jump Game (LeetCode 55)
 * 
 * Given an array where nums[i] = max jump length from position i,
 * determine if you can reach the last index.
 * 
 * ANALYSIS:
 * - State: dp[i] = can we reach position i?
 * - This is 1D (position in array)
 * - Type: Decision problem (boolean DP)
 * - Recurrence: dp[i] = OR(dp[j] AND j + nums[j] >= i) for all j < i
 * - Pattern: All previous lookback (O(n²) naive)
 * 
 * But there's a greedy O(n) solution: track max reachable position!
 */
 
// DP Solution: O(n²) time, O(n) space
function canJumpDP(nums: number[]): boolean {
    const n = nums.length;
    const dp: boolean[] = new Array(n).fill(false);
    dp[0] = true;  // Start position is reachable
    
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (dp[j] && j + nums[j] >= i) {
                dp[i] = true;
                break;  // Found one way, no need to continue
            }
        }
    }
    
    return dp[n - 1];
}
 
// Greedy Solution: O(n) time, O(1) space
function canJumpGreedy(nums: number[]): boolean {
    let maxReach = 0;
    
    for (let i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;  // Can't reach position i
        maxReach = Math.max(maxReach, i + nums[i]);
        if (maxReach >= nums.length - 1) return true;
    }
    
    return true;
}

DP vs Greedy

Some 1D DP problems have greedy O(n) solutions that are more efficient. Jump Game is one example. When analyzing, first ensure you understand the DP approach, then look for greedy optimizations if the problem has special structure.

Summary and Key Takeaways

This module has provided a comprehensive foundation in 1D dynamic programming, building from Fibonacci through Climbing Stairs and House Robber to the general framework of single-index state design.

Key Takeaways — 1D DP Mastery

•State is the key: dp[i] captures the subproblem. 1D means a single integer index suffices.
•Four problem types: Counting (sum), Optimization (min/max), Decision (or), Sequence (extends).
•Three recurrence patterns: Fixed lookback (O(1) transition), All-previous lookback (O(n) transition), Prefix aggregation (running values).
•Space optimization: Lookback of k means O(k) space is achievable via rolling arrays.
•Debugging systematically: Hand-trace small examples, verify base cases, print DP tables.
•Know the limits: 1D DP works when position alone defines the subproblem. Multi-dimensional state needs 2D+ DP.
•Pattern recognition: Most new problems are variations of known patterns. Identify the core structure.

Module Summary — Three Core 1D DP Problems
Problem	Recurrence	Type	Space-Optimized
Fibonacci	dp[i] = dp[i-1] + dp[i-2]	Counting/Computation	O(1)
Climbing Stairs	dp[i] = dp[i-1] + dp[i-2]	Counting	O(1)
House Robber	dp[i] = max(dp[i-1], dp[i-2]+nums[i])	Optimization	O(1)

Module Complete

You've mastered 1D Dynamic Programming! You can now tackle Fibonacci-style counting problems, climbing stairs variations, house robber and its extensions, and recognize when a problem fits the single-index DP framework. The next module extends these concepts to 2D DP with grid paths and Longest Common Subsequence.