DuelCoder
Sign inPlay free
Blind 75 · #49 · 1-D Dynamic Programming

Climbing Stairs

Easy1-D dynamic programmingTime O(n)Space O(1)

Climbing Stairs is an easy 1-D Dynamic Programming problem from the Blind 75. The key pattern is 1-d dynamic programming, and a good solution runs in O(n) time.

Problem

Return the number of distinct ways to climb n steps using moves of one or two steps.

Examples

Example 1

Input

6

Output

13

Example 2

Input

2

Output

2

Example 3

Input

3

Output

3

Approach

The ways to reach a step are the ways to reach the step below plus the step two below, a Fibonacci recurrence kept in two variables.

Pattern1-D dynamic programming
TimeO(n)
SpaceO(1)

Watch out for

Seed the recurrence correctly: one way for step 1, two ways for step 2.

More 1-D Dynamic Programming problems