LeetCode 之 Climbing Stairs （方法2）

96 阅读 0 评论 64 点赞

我是靠谱客的博主冷艳白昼，最近开发中收集的这篇文章主要介绍LeetCode 之 Climbing Stairs （方法2），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

上一次说了自顶向下，没看的可以回去看看

climbing stairs 方法1（自顶向下）

由于本人是学渣，自顶向下太抽象肿么破。。。。尼玛哥教你一个更抽象的，自底向上，自底向上代码比较简单，基本思想一致，弄个数组record记录一下，本人是学渣，代码不是太优化，不过大体上是这样滴：

1 如果n是1，直接返回1，n是2直接返回2

2 如果n>2 , 就是学渣领悟的最高境界了，number（k , n , record ）代表n个台阶前k个已经确定的情况下的可能总数，那么由第一次的超时代码中看到，由number (k,n,record) = number( k+1 , n ) + number ( k+2 , n); ，利用自底向上，先最最底部的，就是number（n -1 , n , record）和 number（n -2 , n , record）了，good，我们知道这个吧：number（n -1 , n , record） = 1 和 number（n -2 , n , record） = 2，不理解的学渣都帮不了。。。。再利用for把所有的record都算出来，那么record[0]代表的就是在有n个台阶的情况下走了0的总情况数，就是我们要求的结果了。。。。

超时代码（部分）

int number (int k, int n){
    if ( k == n-1 ) return 1;
    if ( k == n-2 ) return 2;
    else return number( k+1 , n ) + number ( k+2 , n);
}

正确代码：

class Solution {
public:

    
    
    int climbStairs(int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        
        int record [n];
       
        return number (0 , n , record);
    }
    //共n个台阶，前k个已经决定了策略，总共的爬楼梯可能
    
    int number (int k , int n , int record[]){
        if (n == 1) return 1;
        else if(n==2) return 2;
        
        record [n-1] = 1;
        record [n-2] = 2;
        
        for (int i = 0; i < n - 2 ; i ++ ){
            record[n-i-3] = record[n-i-1]+record[n-i-2]; 
        }
        return record[0];
    }
    
};