DP(动态规划)入门

谈到动态规划，最经典的当然是背包问题，可以百度下<<背包九讲>>。
但是这里不准备从背包问题讲起，主要是觉得用背包问题来讲DP的思想，还不够通俗易懂。

先来看一个金典的算法题：
爬台阶问题
有n个台阶，你每次可以爬1阶或2阶，问：爬到顶总共有多少种爬法？
例子： n = 3
第一种：1 1 1
第二种：2 1
第三种：1 2
总共有3种爬法。

解法一：递归
代码如下：

public int climbStairs(int n) {
    return (n<=2) ? n : climbStairs(n-1) + climbStairs(n-2);
}

如果n=1,只有一种爬法。
如果n=2,有[(1,1),(2)]两种爬法
如果n>2,分两种情况：

• 第一种，最后一次爬了1阶，climbStairs(n-1)
• 第一种，最后一次爬了2阶，climbStairs(n-2)

所以n>2时，climbStairs(n) = climbStairs(n-1) + climbStairs(n-2)；

递归的思想是：至上而下，想求climbStairs(n) ,转化为求climbStairs(n-1)和climbStairs(n-2)的问题

解法二：DP

public int climbStairs(int n) {
    if(n <= 2)  return n;
    //dp[i] = m ,表示高度为i的台阶，有m种爬法
    int[] dp= new int[n+1];
    
    dp[1] = 1; 
    dp[2] = 2;
    
    for(int i=3; i <= n ; i++)
        dp[i] = dp[i-1] + dp[i-2];

    return dp[n];
}

比如这里n=4，数组dp的长度为5，值为:
dp = [0,1,2,3,5]
dp[4]=5，表示高度为4的台阶有5种爬法。

DP的思想是至下而上的，想求dp[n]需要把前面从0到n-1的值全部求出来，而且是从0开始
DP的关键是能否通过之前求的值，推导出当前的值 也就是这行代码：
dp[i] = dp[i-1] + dp[i-2]
如果dp[i]无法通过之前的值求得，那么就无法使用dp求解。
而dp[i] = dp[i-1] + dp[i-2]叫状态转移方程。DP求解的关键就是找到合适的状态转移方程
由于这个问题比较简单，这个状态转移方程很容易理解。

与上一种递归解法相比，它的时间复杂度肯定要低些，但是他需要一个长度为n+1的数组辅助,所以空间复杂度为O(n+1)。

解法三：优化DP的空间复杂度

public int climbStairs(int n) {
    if(n <= 2)
        return n;

    int first = 1;
    int second = 2;
    
    for(int i=3; i <= n ; i++){
        int third = first + second;
        first = second;
        second = third;
    }
    
    return second;
}

对比上面的DP，这里应该很容易理解，由于我们需要的是dp[n],而dp[0~n-1]我们没必要一直存着，空间复用就行。优化后，这里的空间复杂度为O(1)。

从n=4,dp = [0,1,2,3,5]的例子不难看出，[1,2,3,5]其实就是一个斐波那契数列。所以这个题其实就是求解斐波那契数列。以上三种均不是最优解。存在时间复杂度为O(log(n))的解法，感兴趣可以去leetcode上去看看矩阵的解法。

推荐另一道比较有趣的DP算法题：house robber