One-dimensional DP
GOALFill a table from left to right to reach the answer.
You can do DP without recursion: start from the smallest case and fill a table in order. Climbing stairs is the classic — you take 1 or 2 steps at a time, so in how many ways can you climb n stairs?
ON THIS PAGE
//THE EXAMPLE
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n = 6;
vector<long long> ways(n + 1, 0);
ways[0] = 1;
ways[1] = 1;
for (int i = 2; i <= n; i++) {
ways[i] = ways[i - 1] + ways[i - 2];
}
for (int i = 0; i <= n; i++) cout << ways[i] << " ";
cout << endl;
cout << ways[n] << endl;
return 0;
}1 1 2 3 5 8 13 13
//LINE BY LINE
Watch it run
Two starting values: one way to stand still, one way to climb one step.
Finding the rule
All the hard work in DP is in one question: "to be at position i, where could I have come from?" Answer that and the code writes itself.
- 1.Write in words what ONE cell of the table means.
- 2.Ask: to reach here, where could I have come from?
- 3.Add those up (a counting problem) or take the best (an optimisation).
- 4.Fill in the smallest case by hand.
The starting values are where this usually goes wrong. A wrong ways[0] poisons the whole table, and you only notice at the end.
Shrinking the table
When the rule looks back only a step or two, you do not need the whole array. Two variables will do.
// ways[i] = ways[i-1] + ways[i-2] — only two values matter
int a = 1, b = 1;
for (int i = 2; i <= n; i++) {
int next = a + b;
a = b;
b = next;
}Write the full array first, check it, then shrink. And if the problem asks WHICH route, keep the full table — you have to walk back through it.