2Brute2Best
🔥0
01

Fibonacci-style (DP — 1D Linear Sub-pattern)

dp[i] is built from dp[i − 1] and dp[i − 2] only — the last step was a 1-step or a 2-step (or a 1-digit or 2-digit piece).

Signals in the problem statement
  • ›

    "1 or 2 steps at a time"

  • ›

    "number of ways to reach / decode"

  • ›

    "cheapest way to the top"

  • ›

    the answer for n uses the answers for n − 1 and n − 2

What makes it different

The state is just the position. Ask: what was the last move? Each possible last move is one term in the rule. Keep two variables at the end.

Questions

ordered from “learn the idea” to “recognise it without help”
  1. 1
    Climbing Stairs
    Basic Anchor·LeetCode #70
    Easy
  2. 2
    Min Cost Climbing Stairs
    Basic Reinforcement·LeetCode #746
    Easy
  3. 3
    Decode Ways
    Slight Variation·LeetCode #91
    Medium

Template

fibonacci-template.cpp
// Fibonacci-style DP: dp[i] is built from dp[i - 1] and dp[i - 2] only,
// so two variables are enough. Shown for "ways to climb n stairs (1 or 2 steps)".
int climbWays(int n) {
    if (n <= 1) return 1;
    int prev2 = 1, prev1 = 1;          // dp[0], dp[1]
    for (int i = 2; i <= n; i++) {
        int cur = prev1 + prev2;       // last move was a 1-step or a 2-step
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;                      // dp[n]
}
Remember this · DP — 1D Linear
Trigger
"Number of ways", "maximum/minimum up to i", choices at each step that depend on the previous one or two.
Think
If I knew the answer for every smaller prefix, how would I get the answer for i?
Key question
What does dp[i] mean in one sentence?
DP — 1D Linear overviewTake or skip