1-D Dynamic Programming: pattern and problems

Step 1 Understand it

Remember it by
Write what dp[i] means in one sentence, then build it from dp[i − 1] and dp[i − 2].

Watch it happen

Animation1-D DP: each answer is built from answers already saved

Read the animation as text

How many ways to climb 5 steps, taking 1 or 2 at a time? Your last move onto step i came from step i − 1 or step i − 2 — so ways(i) = ways(i − 1) + ways(i − 2).
Base cases: there is 1 way to stand at step 0 (do nothing) and 1 way to reach step 1 (one small step).
dp[2] = dp[1] + dp[0] = 1 + 1 = 2. Both answers were already saved, so this costs one addition.
dp[3] = dp[2] + dp[1] = 2 + 1 = 3. Both answers were already saved, so this costs one addition.
dp[4] = dp[3] + dp[2] = 3 + 2 = 5. Both answers were already saved, so this costs one addition.
dp[5] = dp[4] + dp[3] = 5 + 3 = 8. Both answers were already saved, so this costs one addition.
Answer: 8 ways. Each step is worked out once from saved answers: O(n), instead of the O(2ⁿ) of plain recursion that keeps re-solving the same steps.

The idea

Dynamic programming solves a problem by reusing answers to smaller versions of it. In 1-D, dp[i] is the answer for the first i items (or for amount i). Find the recurrence (how dp[i] comes from earlier entries), set the base cases, and fill the table in order.

Picture it

flowchart LR
  A["dp[i − 2]"] --> C["dp[i]"]
  B["dp[i − 1]"] --> C
  C --> D["dp[i + 1]"]

Each answer is built from the ones just before it, so every sub-question is solved exactly once.

Analogy

Climbing stairs and writing on each step how many ways there are to reach it. To fill in a new step, you just add the numbers on the one or two steps below — no recounting.

Where the analogy breaks

On stairs the earlier numbers are obviously right. In DP you must define dp[i] precisely; if your definition is vague, the recurrence will quietly be wrong.

More detail

What it is

Dynamic Programming (DP) sounds terrifying, but it's actually just one simple idea: 'Don't do the same work twice!' Imagine I ask you to calculate 1+1+1+1. You say '4'. Then I add another '+1' to the end. Do you recount everything from the start? No! You just remember your last answer (4) and add 1 to get 5. That's exactly what DP is: saving the answers to smaller sub-problems exactly once so you can instantly lookup that answer later when solving a bigger problem.

When to use it

When a problem asks for the 'minimum', 'maximum', 'longest', or 'total ways' to do something.
When you notice that a recursive solution calculates the exact same branches multiple times (Overlapping Subproblems).

How it works

There are two ways to do DP.\n1. **Top-Down (Memoization)**: You write a standard recursive function, but you add a HashMap or Array to 'cache' the result before returning. Next time the function is called with those same arguments, you return the cached result instantly.\n2. **Bottom-Up (Tabulation)**: You build an array (usually 1-Dimensional here) starting from index 0. You solve the smallest piece of the puzzle first, then use a for-loop to build up to the final answer.

Example walkthrough

Input: Climbing Stairs: N=3 (can take 1 or 2 steps)

Step 0 or 1: 1 way. dp=[1, 1].
Step 2: Can be reached from step 1 or step 0. So dp[2] = dp[1] + dp[0] = 2. dp=[1,1,2].
Step 3: Can be reached from step 2 or step 1. So dp[3] = dp[2] + dp[1] = 2+1 = 3. dp=[1,1,2,3].
Answer is dp[3], which is 3!

Result: 3

Related patterns

Backtracking: DP is just backtracking with a super-powered memory cache!

Step 2 Recognise it

Words that signal it

'Number of ways' to do something
'Minimum / maximum' cost, profit or count
Choices at each step that affect later choices (rob this house or not)
The brute-force recursion repeats the same sub-question many times

Don't confuse it with

Greedy: If one locally best choice can be wrong later (coins [1, 3, 4] for 6: greedy gives 4 + 1 + 1, DP gives 3 + 3), you need DP.
Backtracking: List all the ways → backtracking. Count them or find the best → DP.

Gut check

Would the brute force ask the same sub-question again and again? → DP.

How to recognise it in an interview

The problem talks about finding 'Max/Min/Longest', 'Number of ways', or involves jumping/taking steps.

Step 3 The template

The general shape. Adapt it to each problem rather than learning one solution per problem.

python

def solve(nums):
    n = len(nums)
    dp = [0] * (n + 1)                 # dp[i] = answer using the first i items  <- write this down!
    dp[0] = ...                        # base case(s)
    for i in range(1, n + 1):
        dp[i] = ...                    # from dp[i - 1], dp[i - 2], ...
    return dp[n]

The same template in Java

text

class Solution {
    // Bottom-Up approach for Climbing Stairs
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

TimeO(n) (or O(n × choices))

SpaceO(n), often O(1) by keeping the last two values

Common mistakes

Never writing down what dp[i] means.
Wrong base cases (dp[0] for climbing stairs is 1: one way to stand still).
In Coin Change, using 0 instead of infinity for 'impossible'.
Using recursion without a cache, resulting in O(2^N) time limit exceeded errors.

Step 4 Watch it run

Two problems, traced step by step exactly as the code runs.

Easy example: Climbing Stairs (1 or 2 steps at a time)

Input: n = 5

step i	how	ways dp[i]
0	base case	1
1	base case	1
2	dp[1] + dp[0] = 1 + 1	2
3	dp[2] + dp[1] = 2 + 1	3
4	dp[3] + dp[2] = 3 + 2	5
5	dp[4] + dp[3] = 5 + 3	8

Result: 8

Notice: To land on step i, your last move came from step i − 1 or i − 2. Add the two counts.

python

def climb_stairs(n):
    a, b = 1, 1                 # ways to reach step 0 and step 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Medium example: House Robber

Input: nums = [2, 7, 9, 3, 1]

house (money)	skip it	rob it	best so far
0 (£2)	skip: 0	rob: 0 + 2 = 2	2
1 (£7)	skip: 2	rob: 0 + 7 = 7	7
2 (£9)	skip: 7	rob: 2 + 9 = 11	11
3 (£3)	skip: 11	rob: 7 + 3 = 10	11
4 (£1)	skip: 11	rob: 11 + 1 = 12	12

Result: 12

Notice: At each house there are only two choices: skip it (keep the best so far) or rob it (add it to the best from two houses back).

python

def rob(nums):
    rob1, rob2 = 0, 0           # best up to two houses back, best up to the last house
    for x in nums:
        rob1, rob2 = rob2, max(rob2, rob1 + x)
    return rob2

1-D Dynamic Programming

Step 1 Understand it

Watch it happen

The idea

Picture it

Analogy

Where the analogy breaks

What it is

When to use it

How it works

Example walkthrough

Related patterns

Step 2 Recognise it

Words that signal it

Don't confuse it with

Gut check

How to recognise it in an interview

Step 3 The template

Common mistakes

Step 4 Watch it run

Easy example: Climbing Stairs (1 or 2 steps at a time)

Medium example: House Robber

Step 5 Practise

Easy

Medium

What to say in the interview

Follow-up prep