（Java）leetcode-70 Climbing Stairs（递归，备忘录，动态规划）

忘是亡心i 2022-03-07 02:04 148阅读 0赞

爬楼梯

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.

Example 1:

Input: 2  
Output: 2  
Explanation: There are two ways to climb to the top.

1.  1 step + 1 step
2.  2 steps

Example 2:

Input: 3  
Output: 3  
Explanation: There are three ways to climb to the top.

1.  1 step + 1 step + 1 step
2.  1 step + 2 steps
3.  2 steps + 1 step

# 思路1 #

用几个例子推导之后发现，这是一个类似斐波那契数列的问题，n为i时，结果为i-1与i-2的和。  
最简单的就是自上而下的递归求解了，但是时间开销比较大

# 代码1 #

class Solution { 
        public int climbStairs(int n) { 
        	if(n == 1)
        		return 1;
        	if(n == 2)
        		return 2;
    
            int res = climbStairs(n-1)+climbStairs(n-2);
    
            return res;
        }
    }

## 提交结果 ##

Time Limit Exceeded 超时

# 思路2 #

采用备忘录式的解法可以节省很多时间，因为求解过程中许多结果存在重复，那么只要把每次求解的结果保存下来，需要用这个结果时直接取出来就好，不必再重复计算了.  
时间复杂度O(n)，空间复杂度O（n）

# 代码2 #

class Solution { 
        public int climbStairs(int n) { 
        	if(n == 1)
        		return 1;
        	if(n == 2)
        		return 2;
        	Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        	map.put(1,1);
        	map.put(2,2);
    
        	for(int i = 3;i < n ; i++){ 
        		map.put(i,map.get(i-1)+map.get(i-2));
        	}
        	return map.get(n-1)+map.get(n-2);
    
        }
    }

## 提交结果 ##

Runtime: 2 ms, faster than 89.09% of Java online submissions for Climbing Stairs.  
Memory Usage: 36.3 MB, less than 54.17% of Java online submissions for Climbing Stairs.  
效果还可以。

# 思路3 （动态规划） #

（以下为翻译，讲得很透彻了）  
这个问题似乎是一个动态的编程问题。提示：标签也暗示了！  
以下是逐步获得解决方案的步骤。

基本情况：  
如果n <= 0，则路数应为零。  
如果n == 1，那么只有1种爬楼梯的方法。  
如果n == 2，那么有两种方法可以爬楼梯。

解决这个问题的关键直觉是，给定一定数量的阶梯n，如果我们知道到达各个点的数量的方式\[n-1\]，\[n-2\]分别表示为n1和n2，那么达到这一点的总方法\[n\]是n1 + n2。**因为从这\[n-1\]一点来说，我们可以采取+1来实现\[n\]。从这\[n-2\]一点来说，我们可以采取+2来实现目标。**

通过上述方法计算的解是完整且非冗余的。这两个解决方案集（n1 和n2）涵盖了有关如何采取最终步骤的所有可能情况。并且在由这两个解决方案集构建的最终解决方案之间不存在重叠，因为它们在最后步骤中不同。

现在给出上述直觉，可以构造一个数组，其中每个节点存储每个数字n的解。或者，如果我们仔细观察它，很明显这基本上是一个斐波纳契数，起始数为1和2，而不是1和1。

以下代码使用了自下而上的动态规划解法，只需要常数级的内存空间来保存下一次计算需要的数字，因此空间复杂度为O（1）。  
时间复杂度为O（n）。相比与上面的可以说是绝佳解法了，并且简洁易懂。

# 代码3 #

class Solution { 
    public int climbStairs(int n) { 
        // base cases
        if(n <= 0) return 0;
    class Solution { 
    public int climbStairs(int n) { 
        // base cases
        if(n <= 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 2;
        
    
        int pre1 = 2;//当前阶的前1阶的走法数（当前阶从n=3开始算）
        int pre2 = 1;//当前阶的前2阶的走法数
        int all_ways = 0;
        
        for(int i=2; i<n; i++){ 
        	all_ways = pre1 + pre2;//当前阶的走法==前1阶+前2阶
    
        	//以下为之后的计算做准备，也就是状态转移
        	//当计算下1阶的走法时，该问题的前2阶就是本次循环中的前1阶
        	//而该问题的前1阶就是本次循环中的当前阶
        	pre2 = pre1;
            pre1 = all_ways;
        }
        return all_ways;
     }
    }

## 提交结果 ##

Runtime: 2 ms, faster than 89.09% of Java online submissions for Climbing Stairs.  
Memory Usage: 36.1 MB, less than 99.44% of Java online submissions for Climbing Stairs.