題目
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb or steps. In how many distinct ways can you climb to the top?
題目大意:每步隻能爬一個或者是兩個台階,爬到頂端n個台階有多少中方法?
思路
利用DP的方法,一個台階的方法次數為1次,兩個台階的方法次數為2個。
n個台階的方法可以了解成上n-2個台階,然後2步直接上最後一步;或者上n-1個台階,再單獨上一步。
公式是S[n] = S[n-1] + S[n-2] S[1] = 1 S[2] = 2
有了上面的思想之後,實作代碼如下:
int climbStairs(int n) {
if(n<){
return ;
}
int *result=(int *)malloc(n*sizeof(int));
if(result==NULL){
exit(EXIT_FAILURE);
}
if(n==||n==){
return n;
}
result[]=;
result[]=;
for(int i=;i<n;i++){
//當S[n] = S[n-1] + S[n-2] S[1] = 1 S[2] = 2
result[i]=result[i-]+result[i-];
}
return result[n-];
}