[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で記録するために変換される.
/**
 * @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];
};