[LeetCode javaScript] 70. 階段を登る
2003 ワード
階段を登っているとします.屋上に着くにはn階が必要です.
毎回1つか2つの階段を登ることができます.屋上に登る方法はいくつありますか?
注:指定されたnは正の整数です.
例1:
入力:2出力:2解釈:屋上に登るには2つの方法があります.1.1次+1次2.2次例2:
入力:3出力:3解釈:3つの方法で屋上に登ることができます.1.1次+1次+1次2.1次+2次3.2次+1次
動的計画でnを求める場合、nは(n+1)+(n+2)と表すことができる:すなわちn層に到達し、n−1層から1層、n−2層から2層の階段を上り、その後問題はn−1を求めるすべての可能+n−2のすべての可能性を1つの配列numsで記録するために変換される.
毎回1つか2つの階段を登ることができます.屋上に登る方法はいくつありますか?
注:指定されたnは正の整数です.
例1:
入力:2出力:2解釈:屋上に登るには2つの方法があります.1.1次+1次2.2次例2:
入力:3出力:3解釈:3つの方法で屋上に登ることができます.1.1次+1次+1次2.1次+2次3.2次+1次
動的計画でnを求める場合、nは(n+1)+(n+2)と表すことができる:すなわちn層に到達し、n−1層から1層、n−2層から2層の階段を上り、その後問題はn−1を求めるすべての可能+n−2のすべての可能性を1つの配列numsで記録するために変換される.
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
//
var nums=[];
nums[1]=1;
nums[2]=2;
var climb=function(arr,i){
if(i==1){
return 1;
}
else if(i==2){
return 2;
}
else{
var dx=i-1;
var dy=i-2;
if(dx>2&&!arr[dx]){
climb(arr,dx);
}
if(dy>2&&!arr[dy]){
climb(arr,dy);
}
nums[i]=nums[dx]+nums[dy];
}
}
climb(nums,n);
return nums[n];
};