您的位置: 首页  >  文章  >  70. Climbing Stairs

70. Climbing Stairs

分类: 文章 • 2024-09-24 11:33:04

第一反应，递归求解，貌似很简单。但是不幸，超时

[java] view plain copy
  1. public int climbStairs1(int n) {  
  2.         if (n == 1 || n == 2) {  
  3.             return n;  
  4.         }  
  5.         return climbStairs1(n-1) + climbStairs1(n-2);  
  6.     }  

为什么超时呢？因为有很多重复的计算，以n=5为例，递归图如下所示：

70. Climbing Stairs


如果所示，标颜色的需要重复递归调用计算，所以动态规划的思想就是把重叠子问题存储下来，下次调用直接查表即可。比如在第一次递归调用时，n=3已经将结果计算出来，在n=4的时候就不需要就算了，上代码：

[java] view plain copy
  1. public int climbStairs(int n) {  
  2.         if (n == 0 || n == 1 || n == 2) {  
  3.             return n;  
  4.         }  
  5.         int[] r = new int[n+1];  
  6.         r[1] = 1;  
  7.         r[2] = 2;  
  8.         for (int i = 3; i <= n; i++) {  
  9.             r[i] = r[i-1] + r[i-2];  
  10.         }  
  11.         return r[n];  
  12.     }  

第三种方法：
同样采用动态规划方法
但是不采用新的数组存放每次多次算法的值，因为只要取出最后一个数就可以。
因此可以直接递推相加。
class Solution {
    public int climbStairs(int n) {
        if (n==0||n==1||n==2)
            return n;
        int one_step=1;
        int two_step=2;
        int all_ways=0;
        for (int i=2;i<n;i++){
            all_ways=one_step+two_step;
            one_step=two_step;
            two_step=all_ways;
        }
        return all_ways;
    }
}

相关推荐