LESSON 27 · PATTERN GUIDE

1D DP Basics

Reuse answers to smaller prefixes or states instead of recomputing the same subproblems.

FIRST, LEARN THE PATTERNDefine dp[i] in one sentence, write the recurrence from earlier states, and set base cases before filling the table.

The task asks for an optimum or number of ways and choices at position i depend on a few earlier positions.

How to approach it

Start with a recurrence and base cases; fill from smallest states upward, then reduce memory only if older values are no longer needed.

Watch out for

A wrong state definition creates a wrong recurrence. Make sure each state captures enough information for future choices.

A CLOSER EXPLANATION

Dynamic programming stores answers to overlapping subproblems. State should capture exactly what future decisions need; the recurrence explains how a larger state uses smaller ones. Base cases anchor the recurrence, and tabulation follows dependency order.

NOW YOU TRY

Practice question

A person can climb 1 or 2 stairs at a time. How many distinct ways are there to reach stair 5?

EXAMPLEn = 5; ways(0) = 1Give your answer before revealing the explanation.

Show a hint

Ways(n) = Ways(n−1) + Ways(n−2).

Show an answer

8 ways.

CONNECT IT TO REAL LIFE

1D DP Basics at work

A worker can accept projects on days with values [4, 7, 3, 8], but cannot work on consecutive days. What is the maximum value they can accept?

Show one possible approach

15, from days with values 7 and 8, which are not consecutive. At each day, choose between skipping it or taking it plus the best value through the day before last.

Practice next

Use these problem IDs to find additional practice for this pattern:

70198213322279300