1D DP is used when the answer for a position/state depends on previous smaller states.

Its biggest advantage:

Solve each smaller state once and reuse the result.

Focus on recognizing:

“Answer at position i depends on previous states” = 1D DP

Core Idea

Most 1D DP problems follow:

Define state
    ↓
Find transition
    ↓
Set base case
    ↓
Build answer
    ↓
Optimize space if possible

Pattern Table

Pattern	Typical Questions	Trigger
Fibonacci	Previous-state recurrence	Depends on previous 1–2 states
Climbing Stairs	Count ways to reach target	Ways / steps / jumps
House Robber	Maximum non-adjacent sum	Take or skip
Kadane	Maximum contiguous sum	Best subarray
Coin Change Min	Minimum coins/operations	Min choices to target
Coin Change Ways	Count combinations	Number of ways
Subset Sum	Target achievable?	Can form target
LIS	Longest increasing subsequence	Increasing + subsequence
Partition	Split into equal sums	Equal partition
Decode Ways	Decode numeric string	1-digit / 2-digit choices

Mental Trigger

Ask:

“Can I define the answer at index/state i using smaller states?”

If yes → think 1D DP.

Generic 1D DP Template

This is the basic template to understand before learning the individual patterns.

public int solve(int n) {
    int[] dp = new int[n + 1];

    // Base case
    dp[0] = 0;

    // Build smaller states first
    for (int i = 1; i <= n; i++) {

        // Transition
        dp[i] = ...;
    }

    return dp[n];
}

def solve(n):
    dp = [0] * (n + 1)

    # Base case
    dp[0] = 0

    # Build smaller states first
    for i in range(1, n + 1):

        # Transition
        dp[i] = ...

    return dp[n]

int solve(int n) {
    vector<int> dp(n + 1);

    // Base case
    dp[0] = 0;

    // Build smaller states first
    for (int i = 1; i <= n; i++) {

        // Transition
        dp[i] = ...;
    }

    return dp[n];
}

function solve(n) {
  const dp = new Array(n + 1).fill(0);

  // Base case
  dp[0] = 0;

  // Build smaller states first
  for (let i = 1; i <= n; i++) {
    // Transition
    dp[i] = ...;
  }

  return dp[n];
}

The important part is not memorizing this exact code.

Instead remember:

dp[i] = answer for state i

Then ask:

How can I calculate dp[i] from previous states?

Pattern 1: Fibonacci

When to use

Fibonacci

Each value is the sum of the previous two.

dp[i] = dp[i-1] + dp[i-2], with base dp[0]=0, dp[1]=1. This is the seed of all 1-D DP: the current state depends on earlier states. O(n) time, O(n) space (or O(1)).

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp[0] = 0
                      
                        2
                        dp[1] = 1
                      
                        3
                        for i in 2..n:
                      
                        4
                          dp[i] = dp[i-1] + dp[i-2]
                      
                        5
                        return dp[n]

Current answer depends on previous states.
Usually previous 1–2 values.
Recurrence-style problems.

Typical Problems

Fibonacci Number
Tribonacci
Simple recurrence problems

Mental Trigger

“Current state depends on previous few states” → Fibonacci DP

Java Template

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

    int prev2 = 0;
    int prev1 = 1;

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

        prev2 = prev1;
        prev1 = cur;
    }

    return prev1;
}

def fib(n):
    if n <= 1:
        return n

    prev2 = 0
    prev1 = 1

    for _ in range(2, n + 1):
        cur = prev1 + prev2

        prev2 = prev1
        prev1 = cur

    return prev1

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

    int prev2 = 0;
    int prev1 = 1;

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

        prev2 = prev1;
        prev1 = cur;
    }

    return prev1;
}

function fib(n) {
  if (n <= 1) {
    return n;
  }

  let prev2 = 0;
  let prev1 = 1;

  for (let i = 2; i <= n; i++) {
    const cur = prev1 + prev2;

    prev2 = prev1;
    prev1 = cur;
  }

  return prev1;
}

What Changed from Generic DP?

Generic:

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

Changed to:

int prev2 = 0;
int prev1 = 1;

because:

dp[i] only needs the previous two states.

So we can optimize:

O(n) space → O(1) space

If only the previous few states are needed, use variables instead of a DP array.

Pattern 2: Climbing Stairs

When to use

Count ways to reach a position.
Each move can come from a small number of previous positions.

Typical Problems

Climbing Stairs
Number of ways to reach N
Min Cost Climbing Stairs

Mental Trigger

“How many ways can I reach this position?” → Climbing Stairs DP

Java Template

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

    int prev2 = 1;
    int prev1 = 1;

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

        prev2 = prev1;
        prev1 = cur;
    }

    return prev1;
}

def climb_stairs(n):
    if n <= 1:
        return 1

    prev2 = 1
    prev1 = 1

    for _ in range(2, n + 1):
        cur = prev1 + prev2

        prev2 = prev1
        prev1 = cur

    return prev1

int climbStairs(int n) {
    if (n <= 1) {
        return 1;
    }

    int prev2 = 1;
    int prev1 = 1;

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

        prev2 = prev1;
        prev1 = cur;
    }

    return prev1;
}

function climbStairs(n) {
  if (n <= 1) {
    return 1;
  }

  let prev2 = 1;
  let prev1 = 1;

  for (let i = 2; i <= n; i++) {
    const cur = prev1 + prev2;

    prev2 = prev1;
    prev1 = cur;
  }

  return prev1;
}

What Changed from Fibonacci?

Fibonacci:

dp[0] = 0;
dp[1] = 1;

Climbing Stairs:

dp[0] = 1;
dp[1] = 1;

because:

0 stairs → 1 way
1 stair  → 1 way

The transition is still:

cur = prev1 + prev2;

Climbing Stairs is basically Fibonacci with different base cases.

Pattern 3: House Robber

When to use

Array of values.
Cannot select adjacent elements.
Maximize total value.

Rob or skip each house — watch greedy grab the wrong house and DP dodge the trap:

House Robber

Maximize loot robbing non-adjacent houses.

dp[i] = max(dp[i−1] (skip), dp[i−2] + nums[i] (rob)). Each house is a take/skip choice; keep only the last two values for O(1) space. Greedy-grabbing the biggest house can block a better combo, which is why DP is needed.

ARRAY VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp[0] = nums[0]
                      
                        2
                        dp[1] = max(nums[0], nums[1])
                      
                        3
                        for i in 2..n-1:
                      
                        4
                          dp[i] = max(
                      
                        5
                            dp[i-1],            // skip house i
                      
                        6
                            dp[i-2] + nums[i]   // rob it
                      
                        7
                          )

Typical Problems

House Robber
Maximum sum of non-adjacent elements
Delete and Earn

Mental Trigger

“Take or skip?” + “Cannot take adjacent” → House Robber DP

Java Template

public int rob(int[] nums) {
    int prev2 = 0;
    int prev1 = 0;

    for (int x : nums) {

        int take = prev2 + x;
        int skip = prev1;

        int cur = Math.max(take, skip);

        prev2 = prev1;
        prev1 = cur;
    }

    return prev1;
}

def rob(nums):
    prev2 = 0
    prev1 = 0

    for x in nums:
        take = prev2 + x
        skip = prev1

        cur = max(take, skip)

        prev2 = prev1
        prev1 = cur

    return prev1

int rob(vector<int>& nums) {
    int prev2 = 0;
    int prev1 = 0;

    for (int x : nums) {

        int take = prev2 + x;
        int skip = prev1;

        int cur = max(take, skip);

        prev2 = prev1;
        prev1 = cur;
    }

    return prev1;
}

function rob(nums) {
  let prev2 = 0;
  let prev1 = 0;

  for (const x of nums) {
    const take = prev2 + x;
    const skip = prev1;

    const cur = Math.max(take, skip);

    prev2 = prev1;
    prev1 = cur;
  }

  return prev1;
}

What Changed from Fibonacci?

Fibonacci:

cur = prev1 + prev2;

House Robber:

int take = prev2 + x;
int skip = prev1;

int cur = Math.max(take, skip);

because we have a decision:

Take current
    → previous element cannot be taken

Skip current
    → keep previous answer

Take/Skip + adjacency restriction = House Robber DP.

Pattern 4: Maximum Subarray — Kadane’s Algorithm

When to use

Maximum Subarray (Kadane)

Largest sum of any contiguous subarray.

Keep cur = max(x, cur+x); if carrying the run forward hurts, restart at x. best tracks the max seen. Seed best with the first element (or −∞) so all-negative arrays work. O(n) time, O(1) space.

ARRAY VISUALIZER

Steps –

-2

-3

-1

-5

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        cur = 0, best = -infinity
                      
                        2
                        for x in nums:
                      
                        3
                          cur = max(x, cur + x)
                      
                        4
                          best = max(best, cur)
                      
                        5
                        return best

Need maximum sum.
Subarray must be contiguous.
Values may be positive or negative.

Typical Problems

Maximum Subarray
Largest contiguous sum
Maximum circular subarray variation

Mental Trigger

“Maximum contiguous segment” → Kadane

Java Template

public int maxSubArray(int[] nums) {
    int cur = nums[0];
    int best = nums[0];

    for (int i = 1; i < nums.length; i++) {

        cur = Math.max(nums[i], cur + nums[i]);

        best = Math.max(best, cur);
    }

    return best;
}

def max_sub_array(nums):
    cur = nums[0]
    best = nums[0]

    for i in range(1, len(nums)):
        cur = max(nums[i], cur + nums[i])

        best = max(best, cur)

    return best

int maxSubArray(vector<int>& nums) {
    int cur = nums[0];
    int best = nums[0];

    for (int i = 1; i < (int)nums.size(); i++) {

        cur = max(nums[i], cur + nums[i]);

        best = max(best, cur);
    }

    return best;
}

function maxSubArray(nums) {
  let cur = nums[0];
  let best = nums[0];

  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]);

    best = Math.max(best, cur);
  }

  return best;
}

What Changed from House Robber?

House Robber asks:

Take or skip

Kadane asks:

Extend current subarray
OR
Start a new subarray

So:

cur = Math.max(nums[i], cur + nums[i]);

Kadane = Extend previous subarray or start fresh.

Pattern 5: Coin Change — Minimum Coins

When to use

Need minimum number of choices.
Choices can usually be reused.
Need to reach a target amount.

The dp table where greedy biggest-coin-first famously fails (6 = 3+3 beats 4+1+1):

Coin Change (Min Coins)

Fewest coins that make a given amount, or report impossible.

dp[a] = min coins for amount a. For each amount try every coin ≤ a: dp[a] = min(dp[a], dp[a−c]+1). The ∞ sentinel means unreachable. Greedy-by-largest-coin fails here — dp[6] with coins [1,3,4] is 2 (3+3), not 3 (4+1+1).

ARRAY VISUALIZER

Steps –

∞

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp[0] = 0   // zero coins make amount 0
                      
                        2
                        for a in 1..amount:
                      
                        3
                          for c in coins:
                      
                        4
                            if c <= a:
                      
                        5
                              dp[a] = min(dp[a], dp[a-c] + 1)

Typical Problems

Coin Change
Minimum number of perfect squares
Minimum operations to reach target

Mental Trigger

“Minimum choices to reach target” → Min DP

Java Template

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];

    Arrays.fill(dp, amount + 1);

    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {

        for (int coin : coins) {

            if (coin <= i) {
                dp[i] = Math.min(
                    dp[i],
                    dp[i - coin] + 1
                );
            }
        }
    }

    return dp[amount] > amount ? -1 : dp[amount];
}

def coin_change(coins, amount):
    dp = [amount + 1] * (amount + 1)

    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return -1 if dp[amount] > amount else dp[amount]

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);

    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {

        for (int coin : coins) {

            if (coin <= i) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] > amount ? -1 : dp[amount];
}

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(amount + 1);

  dp[0] = 0;

  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  return dp[amount] > amount ? -1 : dp[amount];
}

What Changed from Generic DP?

Generic:

dp[i] = ...

Changed to:

dp[i] = Math.min(dp[i], dp[i - coin] + 1);

because:

We want the minimum number of choices.

State Meaning

dp[i] = minimum coins needed to make amount i

Minimize → initialize with a large value → use Math.min().

Pattern 6: Coin Change — Count Ways

When to use

Coin Change — Count Ways

Number of combinations to make each amount with coins {1,2}.

dp[amt] = number of ways to form `amt`. Process coins one by one; for each coin, dp[amt] += dp[amt - coin] (unbounded reuse). Order-independent because coins are fixed before amounts. O(coins·amount) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp[0] = 1
                      
                        2
                        for coin in coins:
                      
                        3
                          for amt in coin..target:
                      
                        4
                            dp[amt] += dp[amt - coin]
                      
                        5
                        return dp[target]

Need number of combinations.
Choices can be reused.
Order usually does NOT matter.

Typical Problems

Coin Change II
Count combinations to form amount

Mental Trigger

“How many combinations can form this target?” → Count Ways DP

Java Template

public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];

    dp[0] = 1;

    for (int coin : coins) {

        for (int i = coin; i <= amount; i++) {

            dp[i] += dp[i - coin];
        }
    }

    return dp[amount];
}

def change(amount, coins):
    dp = [0] * (amount + 1)

    dp[0] = 1

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]

int change(int amount, vector<int>& coins) {
    vector<int> dp(amount + 1, 0);

    dp[0] = 1;

    for (int coin : coins) {

        for (int i = coin; i <= amount; i++) {

            dp[i] += dp[i - coin];
        }
    }

    return dp[amount];
}

function change(amount, coins) {
  const dp = new Array(amount + 1).fill(0);

  dp[0] = 1;

  for (const coin of coins) {
    for (let i = coin; i <= amount; i++) {
      dp[i] += dp[i - coin];
    }
  }

  return dp[amount];
}

What Changed from Min Coin?

Minimum:

dp[i] = Math.min(...);

Count:

dp[i] += dp[i - coin];

because:

We are adding the number of ways.

The coin loop is outside:

for (int coin : coins)

to count combinations rather than different orders.

Count ways → dp[i] += dp[i - choice].

Pattern 7: Subset Sum

When to use

Subset Sum

Can a subset of the numbers exactly reach the target?

dp[j] = true if amount j is reachable. dp[0]=true. For each num, update backward (0/1, no reuse): dp[j] |= dp[j - num]. O(n·target) time, O(target) space.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp[0] = true
                      
                        2
                        for num in nums:
                      
                        3
                          for j from target down to num:
                      
                        4
                            dp[j] |= dp[j - num]
                      
                        5
                        return dp[target]

Given numbers.
Need to know whether a target sum can be formed.
Each number can normally be used once.

Typical Problems

Subset Sum
Target Sum variations
0/1 Knapsack feasibility

Mental Trigger

“Can I form this target using each element at most once?” → Subset DP

Java Template

public boolean subsetSum(int[] nums, int target) {
    boolean[] dp = new boolean[target + 1];

    dp[0] = true;

    for (int x : nums) {

        for (int sum = target; sum >= x; sum--) {

            dp[sum] = dp[sum] || dp[sum - x];
        }
    }

    return dp[target];
}

def subset_sum(nums, target):
    dp = [False] * (target + 1)

    dp[0] = True

    for x in nums:
        for s in range(target, x - 1, -1):
            dp[s] = dp[s] or dp[s - x]

    return dp[target]

bool subsetSum(vector<int>& nums, int target) {
    vector<bool> dp(target + 1, false);

    dp[0] = true;

    for (int x : nums) {

        for (int s = target; s >= x; s--) {

            dp[s] = dp[s] || dp[s - x];
        }
    }

    return dp[target];
}

function subsetSum(nums, target) {
  const dp = new Array(target + 1).fill(false);

  dp[0] = true;

  for (const x of nums) {
    for (let s = target; s >= x; s--) {
      dp[s] = dp[s] || dp[s - x];
    }
  }

  return dp[target];
}

What Changed from Coin Change?

Coin Change:

for (int i = coin; i <= amount; i++)

Subset Sum:

for (int sum = target; sum >= x; sum--)

The loop goes backward because:

Each number can only be used once.

Forward iteration could reuse the same number multiple times.

0/1 choice → iterate target backward.

Pattern 8: Partition Equal Subset Sum

When to use

Partition Equal Subset Sum

Split a set into two subsets with equal sum.

Equivalent to subset-sum to total/2. If total is odd, impossible. Build reachable sums with 0/1 knapsack; answer = dp[total/2]. O(n·sum) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        if sum(nums) % 2 != 0: return false
                      
                        2
                        target = sum / 2
                      
                        3
                        dp[0] = true
                      
                        4
                        for num in nums:
                      
                        5
                          for j from target down to num:
                      
                        6
                            dp[j] |= dp[j - num]
                      
                        7
                        return dp[target]

Split numbers into two groups.
Both groups must have equal sum.

Mental Trigger

“Can I split the array into two equal-sum groups?” → Subset Sum DP

Java Template

public boolean canPartition(int[] nums) {
    int total = 0;

    for (int x : nums) {
        total += x;
    }

    if ((total & 1) == 1) {
        return false;
    }

    int target = total / 2;

    boolean[] dp = new boolean[target + 1];

    dp[0] = true;

    for (int x : nums) {

        for (int sum = target; sum >= x; sum--) {

            dp[sum] = dp[sum] || dp[sum - x];
        }
    }

    return dp[target];
}

def can_partition(nums):
    total = 0

    for x in nums:
        total += x

    if total & 1:
        return False

    target = total // 2

    dp = [False] * (target + 1)

    dp[0] = True

    for x in nums:
        for s in range(target, x - 1, -1):
            dp[s] = dp[s] or dp[s - x]

    return dp[target]

bool canPartition(vector<int>& nums) {
    int total = 0;

    for (int x : nums) {
        total += x;
    }

    if (total & 1) {
        return false;
    }

    int target = total / 2;

    vector<bool> dp(target + 1, false);

    dp[0] = true;

    for (int x : nums) {

        for (int s = target; s >= x; s--) {

            dp[s] = dp[s] || dp[s - x];
        }
    }

    return dp[target];
}

function canPartition(nums) {
  let total = 0;

  for (const x of nums) {
    total += x;
  }

  if ((total & 1) === 1) {
    return false;
  }

  const target = total / 2;

  const dp = new Array(target + 1).fill(false);

  dp[0] = true;

  for (const x of nums) {
    for (let s = target; s >= x; s--) {
      dp[s] = dp[s] || dp[s - x];
    }
  }

  return dp[target];
}

What Changed from Subset Sum?

Subset Sum already asks:

Can I make target?

Partition first converts:

total sum

into:

target = total / 2

Then it uses the exact same subset-sum DP.

Equal partition → Total must be even → Find subset with sum / 2.

Pattern 9: Longest Increasing Subsequence — LIS

When to use

Sequence/array.
Need longest increasing subsequence.
Elements do not have to be contiguous.

Typical Problems

Longest Increasing Subsequence
Number of LIS
Russian Doll Envelopes variations

Mental Trigger

“Longest + increasing + subsequence” → LIS DP

Java Template

public int lengthOfLIS(int[] nums) {
    int n = nums.length;

    int[] dp = new int[n];

    int best = 0;

    for (int i = 0; i < n; i++) {

        dp[i] = 1;

        for (int j = 0; j < i; j++) {

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

        best = Math.max(best, dp[i]);
    }

    return best;
}

def length_of_lis(nums):
    n = len(nums)

    dp = [0] * n

    best = 0

    for i in range(n):
        dp[i] = 1

        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

        best = max(best, dp[i])

    return best

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();

    vector<int> dp(n);

    int best = 0;

    for (int i = 0; i < n; i++) {

        dp[i] = 1;

        for (int j = 0; j < i; j++) {

            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        best = max(best, dp[i]);
    }

    return best;
}

function lengthOfLIS(nums) {
  const n = nums.length;

  const dp = new Array(n).fill(0);

  let best = 0;

  for (let i = 0; i < n; i++) {
    dp[i] = 1;

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

    best = Math.max(best, dp[i]);
  }

  return best;
}

What Changed from Previous 1DP Patterns?

Instead of:

dp[i] depends only on i-1

LIS checks:

for (int j = 0; j < i; j++)

because the previous valid element could be any earlier index.

State Meaning

dp[i] = longest increasing subsequence ending at i

LIS = Try every earlier smaller element → extend the best sequence.

Pattern 10: Decode Ways

When to use

Decode Ways

Number of ways to decode a digit string (1–26 → A–Z).

dp[i] = ways to decode prefix of length i. If digit i alone valid (1–9) add dp[i−1]; if two-digit 10–26 valid add dp[i−2]. O(n) time, O(1) rolling space.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp[0] = 1 (empty prefix)
                      
                        2
                        for i in 1..n:
                      
                        3
                          if s[i] in '1'..'9': dp[i] += dp[i-1]
                      
                        4
                          if s[i-1..i] in '10'..'26': dp[i] += dp[i-2]
                      
                        5
                        return dp[n]

Input is a numeric string.
Digits map to letters.
Need number of valid decodings.
One digit or two digits can form a valid choice.

Typical Problems

Decode Ways
Message decoding
Digit-to-letter mapping

Mental Trigger

“How many ways can this digit string be decoded?” → Decode DP

Java Template

public int numDecodings(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }

    if (s.charAt(0) == '0') {
        return 0;
    }

    int prev2 = 1;
    int prev1 = 1;

    for (int i = 1; i < s.length(); i++) {

        int cur = 0;

        int one = s.charAt(i) - '0';

        int two =
            (s.charAt(i - 1) - '0') * 10 + one;

        // Use current digit alone
        if (one >= 1 && one <= 9) {
            cur += prev1;
        }

        // Use two digits together
        if (two >= 10 && two <= 26) {
            cur += prev2;
        }

        prev2 = prev1;
        prev1 = cur;
    }

    return prev1;
}

def num_decodings(s):
    if not s:
        return 0

    if s[0] == '0':
        return 0

    prev2 = 1
    prev1 = 1

    for i in range(1, len(s)):
        cur = 0

        one = int(s[i])

        two = int(s[i - 1]) * 10 + one

        # Use current digit alone
        if 1 <= one <= 9:
            cur += prev1

        # Use two digits together
        if 10 <= two <= 26:
            cur += prev2

        prev2 = prev1
        prev1 = cur

    return prev1

int numDecodings(string s) {
    if (s.empty()) {
        return 0;
    }

    if (s[0] == '0') {
        return 0;
    }

    int prev2 = 1;
    int prev1 = 1;

    for (int i = 1; i < (int)s.size(); i++) {

        int cur = 0;

        int one = s[i] - '0';

        int two =
            (s[i - 1] - '0') * 10 + one;

        // Use current digit alone
        if (one >= 1 && one <= 9) {
            cur += prev1;
        }

        // Use two digits together
        if (two >= 10 && two <= 26) {
            cur += prev2;
        }

        prev2 = prev1;
        prev1 = cur;
    }

    return prev1;
}

function numDecodings(s) {
  if (!s) {
    return 0;
  }

  if (s[0] === '0') {
    return 0;
  }

  let prev2 = 1;
  let prev1 = 1;

  for (let i = 1; i < s.length; i++) {
    let cur = 0;

    const one = +s[i];

    const two = +s[i - 1] * 10 + one;

    // Use current digit alone
    if (one >= 1 && one <= 9) {
      cur += prev1;
    }

    // Use two digits together
    if (two >= 10 && two <= 26) {
      cur += prev2;
    }

    prev2 = prev1;
    prev1 = cur;
  }

  return prev1;
}

What Changed from Fibonacci?

Fibonacci has:

cur = prev1 + prev2;

Decode Ways conditionally adds them:

if (one is valid)
    cur += prev1;

if (two is valid)
    cur += prev2;

because:

1 digit → one possible transition

2 digits → another possible transition

Decode Ways = Count valid 1-digit and 2-digit transitions.

Pattern 11: Min Cost Climbing Stairs

This is a useful variation of the Climbing Stairs pattern.

When to use

Every position has a cost.
You can move 1 or 2 steps.
Need minimum total cost.

Mental Trigger

“Reach the top with minimum cost” → Climbing Stairs + Min DP

Java Template

public int minCostClimbingStairs(int[] cost) {
    int prev2 = 0;
    int prev1 = 0;

    for (int i = 2; i <= cost.length; i++) {

        int takeOne =
            prev1 + cost[i - 1];

        int takeTwo =
            prev2 + cost[i - 2];

        int cur = Math.min(takeOne, takeTwo);

        prev2 = prev1;
        prev1 = cur;
    }

    return prev1;
}

def min_cost_climbing_stairs(cost):
    prev2 = 0
    prev1 = 0

    for i in range(2, len(cost) + 1):
        take_one = prev1 + cost[i - 1]

        take_two = prev2 + cost[i - 2]

        cur = min(take_one, take_two)

        prev2 = prev1
        prev1 = cur

    return prev1

int minCostClimbingStairs(vector<int>& cost) {
    int prev2 = 0;
    int prev1 = 0;

    for (int i = 2; i <= (int)cost.size(); i++) {

        int takeOne =
            prev1 + cost[i - 1];

        int takeTwo =
            prev2 + cost[i - 2];

        int cur = min(takeOne, takeTwo);

        prev2 = prev1;
        prev1 = cur;
    }

    return prev1;
}

function minCostClimbingStairs(cost) {
  let prev2 = 0;
  let prev1 = 0;

  for (let i = 2; i <= cost.length; i++) {
    const takeOne = prev1 + cost[i - 1];

    const takeTwo = prev2 + cost[i - 2];

    const cur = Math.min(takeOne, takeTwo);

    prev2 = prev1;
    prev1 = cur;
  }

  return prev1;
}

What Changed from Climbing Stairs?

Climbing Stairs:

cur = prev1 + prev2;

Min Cost:

cur = Math.min(
    prev1 + cost[i - 1],
    prev2 + cost[i - 2]
);

because:

We are minimizing cost instead of counting ways.

Same state structure, different operation: count → +, minimum → Math.min().

Climbing Stairs two ways: plain recursion’s exponential re-computation vs. memoized DP’s linear fill. Press ▶ to animate.

Climbing Stairs

Count ways to reach the top taking 1 or 2 steps — recursion vs O(1) tabulation.

climb(n) = climb(n−1) + climb(n−2) with base climb(0)=climb(1)=1. The recursion tree shows every subproblem; memoizing (top-down) or rolling two variables (bottom-up) collapses the O(2ⁿ) tree to O(n). The counts are Fibonacci.

TREE VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        climb(n):
                      
                        2
                          if n <= 1: return 1
                      
                        3
                          return climb(n-1) + climb(n-2)

1DP Pattern Evolution

Generic DP
    ↓
Previous states
    ↓
Fibonacci
    (+ previous 1–2 states)

Climbing Stairs
    (+ different base cases)

House Robber
    (+ take / skip)

Kadane
    (+ extend / restart)

Coin Change Min
    (+ minimize)

Coin Change Ways
    (+ count)

Subset Sum
    (+ boolean feasibility)

Partition
    (+ reduce target to total / 2)

LIS
    (+ check all previous positions)

Decode Ways
    (+ conditional 1-step / 2-step transitions)

Min Cost Stairs
    (+ minimize path cost)

Common Mistakes

1. Not defining the state

Wrong:

int[] dp = new int[n];

without knowing what it means.

Correct:

dp[i] = answer for state i

2. Wrong base case

The transition can be correct but still produce the wrong answer if the base case is wrong.

Always ask:

What should dp[0] mean?

3. Using forward iteration for 0/1 choices

Wrong:

for (int sum = x; sum <= target; sum++)

This can reuse the same element.

Correct:

for (int sum = target; sum >= x; sum--)

4. Confusing subarray and subsequence

Subarray

Must be contiguous:

[2, 3, 4]

Think:

Kadane

Subsequence

Does not need to be contiguous:

[2, 5, 8]

Think:

LIS / subsequence DP

5. Confusing counting and optimization

Count

dp[i] += ...

Minimum

dp[i] = Math.min(...)

Maximum

dp[i] = Math.max(...)

Feasibility

dp[i] = dp[i] || ...

Recognition Cheat Sheet

If you see…	Think…
Previous 1–2 states	Fibonacci
Ways to reach position	Climbing Stairs
Take or skip + no adjacent	House Robber
Maximum contiguous sum	Kadane
Minimum choices to target	Coin Change Min
Number of combinations	Coin Change Ways
Can target sum be formed?	Subset Sum
Split into equal sums	Partition DP
Longest increasing subsequence	LIS
Numeric string + decoding	Decode Ways
Minimum cost to reach top	Min Cost Climbing Stairs

Count vs Min vs Max vs Boolean

A very useful way to recognize DP is to look at what the answer is asking for.

Count

dp[i] += ...

Examples:

Climbing Stairs
Coin Change Ways
Decode Ways

Minimum

dp[i] = Math.min(...)

Examples:

Coin Change
Min Cost Climbing Stairs

Maximum

dp[i] = Math.max(...)

Examples:

House Robber
Kadane
LIS

Boolean

dp[i] = dp[i] || ...

Examples:

Subset Sum
Partition Equal Subset Sum

Earn Premium with Referrals

Core Idea

Pattern Table

Mental Trigger

Generic 1D DP Template

Pattern 1: Fibonacci

When to use

Fibonacci

Typical Problems

Mental Trigger

Java Template

What Changed from Generic DP?

Pattern 2: Climbing Stairs

When to use

Typical Problems

Mental Trigger

Java Template

What Changed from Fibonacci?

Pattern 3: House Robber

When to use

House Robber

Typical Problems

Mental Trigger

Java Template

What Changed from Fibonacci?

Pattern 4: Maximum Subarray — Kadane’s Algorithm

When to use

Maximum Subarray (Kadane)

Typical Problems

Mental Trigger

Java Template

What Changed from House Robber?

Pattern 5: Coin Change — Minimum Coins

When to use

Coin Change (Min Coins)

Typical Problems

Mental Trigger

Java Template

What Changed from Generic DP?

State Meaning

Pattern 6: Coin Change — Count Ways

When to use

Coin Change — Count Ways

Typical Problems

Mental Trigger

Java Template

What Changed from Min Coin?

Pattern 7: Subset Sum

When to use

Subset Sum

Typical Problems

Mental Trigger

Java Template

What Changed from Coin Change?

Pattern 8: Partition Equal Subset Sum

When to use

Partition Equal Subset Sum

Mental Trigger

Java Template

What Changed from Subset Sum?

Pattern 9: Longest Increasing Subsequence — LIS

When to use

Typical Problems

Mental Trigger

Java Template

What Changed from Previous 1DP Patterns?

State Meaning

Pattern 10: Decode Ways

When to use

Decode Ways

Typical Problems

Mental Trigger

Java Template

What Changed from Fibonacci?

Pattern 11: Min Cost Climbing Stairs

When to use

Mental Trigger

Java Template

What Changed from Climbing Stairs?

Climbing Stairs