leetcode 笔记

class Solution {
    //逆向递归方法会超时
    // public int climbStairs(int n) {
    //     if (n==1) return 1;
    //     if (n==2) return 2;
    //     return climbStairs(n-1) + climbStairs(n-2);
    // }
    
//     //顺向累加可以
//     public int climbStairs(int n) {
//         if (n==1) return 1;
//         int last = 1, lastlast = 1;
//         int now = 0;
//         for(int i=2;i<=n;i++){
//             now = last + lastlast;
//             lastlast = last;
//             last = now;
//         }
//         return now;
        
//     }
    
    //记忆化搜索，每一步都记录下来了
    public int climbStairs(int n) {
        int[] result = new int[n+2];
        result[1] = 1;
        result[2] = 2;
        for(int i=3;i<=n;i++){
            result[i] = result[i-1] + result[i-2];
        }
        
        return result[n];
    }
    
    
}