A small problem that shows the whole DP recipe in three lines.
What to build
A table that counts the ways of climbing a staircase.
Requirements
- Each move climbs 1 or 2 stairs.
- Fill a table from the bottom up.
- Print the number of different ways to reach the top.
Input
One number n, the number of stairs.
Output
The number of ways.
Constraints
1 ≤ n ≤ 45.
Example
Input:
3
Output:
3
Why it works
Every way of reaching stair i ends with a move from stair i − 1 or i − 2, and those two groups do not overlap. So the counts add up, and each is worked out only once.
Examples
Example 1 · Input
3
Expected output
3
Example 2 · Input
5
Expected output
8
Hints
Hint 1
The last move was either 1 stair or 2 stairs.
Hint 2
So `ways[i] = ways[i - 1] + ways[i - 2]`, with `ways[0] = 1` and `ways[1] = 1`.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n;
scanf("%d", &n);
int ways[46];
ways[0] = 1;
ways[1] = 1;
for (int i = 2; i <= n; i++) ways[i] = ways[i - 1] + ways[i - 2];
printf("%d\n", ways[n]);
return 0;
}