初始DP

2020-04-09

初识DP

Leetcode 70、爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

假设一共有10层楼梯

如果我们还差最后一步爬完，此时有几种情况呢？
- 不难想象，我们要么在第8阶，要么在第9阶。
接下来我们考虑这样一种情况，我们假设从1-8有x种爬法，从1-9有y种爬法，那么从1-10一共有多少种爬法呢
- 可能结果有一点绕。但只要我们用心思考，不难发现从1-10一共有x+y种爬法。
- 即F(10)=F(9)+F(8)

通过以上的分析，很容易的，我们可以用递归来实现这个过程

暴力递归

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

当然，上述操作的时间复杂度为O(2^n)。

记忆化搜索

递归操作总是会访问到很多重复的结果，我们可以采用记忆搜索的方式，将重复的值存储起来，这样可以一次访问.

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

当然，此时的性能还不是最优。我们可以正向来思考这个过程

动态规划

由于我们在上面推论出F(10)=F(9)+F(8)
当n=3时，不是有F(3)=F(1)+F(2)吗,然后F(4)=F(3)+F(2)
这就跟斐波那契数列一样,我们可以这样实现

class Solution {
    public int climbStairs(int n) {
        if(n==0) return 1;
        if(n<=2) return n;
       int first=1;
       int second=2;
       int sum=0;
       for(int i=3;i<=n;i++){
           sum=first+second;
           first=second;
           second=sum;
       }
       return second;
       
    }
}

或许这并不是真正的“动态规划”，但是我们还是一步步的由最开始的 “暴力递归”->“记忆化搜索”,再到现在的这个情形。

在后面我将详细来介绍动态规划！