Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Notes:
- Coordinate DP
- Space optimization
public int climbStairs(int n) {
if (n <= 1) {
return 1;
}
// state
int[] f = new int[n];
// initialize
f[0] = 1;
f[1] = 2;
// function
for (int i = 2; i < n; ++i) {
f[i] = f[i-1] + f[i-2];
}
// answer
return f[n-1];
}
public int climbStairs(int n) {
if (n <= 1) {
return 1;
}
int lastLast = 1;
int last = 2;
// function
int current = 2;
for (int i = 2; i < n; ++i) {
current = last + lastLast;
lastLast = last;
last = current;
}
// answer
return current;
}