https://leetcode.com/problems/climbing-stairs/description/
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?
Note: Given n will be a positive integer.
Example 1:
Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps
Example 2:
Input: 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step
中文翻譯:
爬樓梯時你可以一次爬一階或兩階。問你今天樓梯有N階，你有幾種爬法 ?
[Solution]
Dynamic programming. Answer of K is based on answer of K-1 and answer of K-2.
This is a basic dynamic programming problem.
The answer of 'K' can be found by combining some of the answer for smaller and similar problem , which you already have.
In this problem, solution of 'K' can be found by combining solution of 'K-1' & 'K-2'.
To move to stair K, you can,
1.Climb 2 stair to reach K, which means you have to reach K-2 first.
2.Climb 1 stair to reach K, which means you have to reach K-1 first.
So the ways to climb to K is the sum of case1 and case2.
The interest thing is that there are two ways to implement Dynamic programming.
A.Top down : Recursion.
B.Bottom up : Build reference table.
Let's implement both of them.
class Solution {
public:
int climbStairs(int n){
return climbStairs_method3_optimize_table(n);
}
int climbStairs_method3_optimize_table(int n){
//this is a bottom up method, and optimize table size
if(n==0) return 0;
if(n==1) return 1;
if(n==2) return 2;
//base case for stair '3'
int two_stair_before_me=1;//the number of ways to climb to K-2
int one_stair_before_me=2;//the number of ways to climb to K-1
int ans;
for(int i=3;i<=n;i++){
// solution(K-2) + solution(K-1)
ans = two_stair_before_me + one_stair_before_me;
//we are move forward, so update the solution of k-2,k-1
two_stair_before_me = one_stair_before_me;
one_stair_before_me = ans;
}
return ans;
}
int climbStairs_method2_table(int n){
//this is a bottom up method
int table[n+1];
table[0]=1;
table[1]=1;
for(int i=2;i<=n;i++)
table[i]=table[i-1]+table[i-2];
return table[n];
}
int climbStairs_method1_recursive(int n) {
if(n==0)
return 0;
else if(n==1)
return 1;
else if(n==2)
return 2;
else
return climbStairs_method1_recursive(n-1)+climbStairs_method1_recursive(n-2);
}
};
