ClimbingStairs [source code]

public class ClimbingStairs {
static

public class Solution {
    public int climbStairs(int n) {
        int[] memo = new int[Math.max(n + 1, 3)];
        memo[0] = 0;
        memo[1] = 1;
        memo[2] = 2;
        for (int i = 3; i < n + 1; i++) {
            memo[i] = memo[i - 2] + memo[i - 1];
        }
        return memo[n];
    }
}

    public static void main(String[] args) {
        ClimbingStairs.Solution tester = new ClimbingStairs.Solution();
    }
}

这个题目总体来说还是很简单的, 就是一个直接了当的 DP 题, DP 题, 我们说过, 一般搞清楚 memo 的维度和 index 就行了. 这里的维度只要1就足够了. 所需要做的 DP decision 也很简单直观.

需要注意的一个小细节, memo 的长度一般是n+1这样的级别, 当时463上课的时候给的几个例子当时也是这么设置表格的大小的. 另外这里为了处理 boundary case, 实际的 memo 长度要有一个下限值.

最后的速度是0(13), 很标准.

这个代码还是可以优化的, space 可以优化到O(1), 只维护两个指针就行了. 不过无论是你平时练习, 还是真正面试的时候都不要急于求成, 先从基本的版本开始写. 然后再优化, 这个才是正确的思路;

感觉这个题目可以用DFS 来做, 虽然未必是最优解, 不过是一个值得锻炼的思路;

以下是 editorial 给出的不同答案, 对于学习思路还是很有帮助的:

Approach #1 Brute Force [Time Limit Exceeded]  

public class Solution {  
    public int climbStairs(int n) {  
        climb_Stairs(0, n);  
    }  
    public int climb_Stairs(int i, int n) {  
        if (i > n) {  
            return 0;  
        }  
        if (i == n) {  
            return 1;  
        }  
        return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n);  
    }  
}

这里他叫做 bruteforce, 其实这个解就是一个标准的 dfs;

Approach #2 Recursion with memorization [Accepted]  

public class Solution {  
    public int climbStairs(int n) {  
        int memo[] = new int[n + 1];  
        return climb_Stairs(0, n, memo);  
    }  
    public int climb_Stairs(int i, int n, int memo[]) {  
        if (i > n) {  
            return 0;  
        }  
        if (i == n) {  
            return 1;  
        }  
        if (memo[i] > 0) {  
            return memo[i];  
        }  
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);  
        return memo[i];  
    }  
}

价格 memo 优化一下, 这个也是一个很正常的优化; 甚至, 以后别人让你优化 DFS, 一个思路方向可能就是假如 memo;

Approach3就是 DP, Approach4就是空间优化之后的 DP, 他们叫做 fibonacci number的方法;

后面两个方法就比较无聊了, 就是专门针对 fibonacci 数列的计算的优化方法而已; 不过时间都做到了O(lgn), 空间都是O(1);

Problem Description

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Difficulty:Easy
Category:Algorithms
Acceptance:39.68%
Contributor: LeetCode
Companies
adobe apple
Related Topics
dynamic programming