LeetCode：动态规划（一）

什么是动态规划？动态规划通常是基于一个递推公式及一个或多个初始化状态。把原问题分解为子问题，求解子问题的最优解。动态规划算法对每个子问题只求解一次，将其结果保存起来，从而避免每次遇到各个子问题时重新计算答案。talk is cheap ,show me your example。个人一直都认为，要搞懂某个问题，通过实例讲解的方式来理解最为有效。这里主要列举一些动规的面试题，剑指offer上有一些题，LeetCode上也选了一些题。

例题1、爬楼梯问题 LeetCode 70

经典的dp入门题，一共有n阶台阶，我们一次可以上一阶或者两阶，问一共有多少种上楼梯的方法。

分析：由于每次最多爬2阶，楼梯的第i阶，只可能是从楼梯的第i-1阶和第i-2阶到达，因此，到达第i阶的爬法只与第i-1阶，第i-2阶的爬法数量直接相关。

$第i阶的爬法数量=第i-1阶爬法数量+第i-2阶爬法数量$

思路：1）设置递归数组，dp[0…n]，dp[i]代表达到第i阶，初始化数组元素为0；2）设置到达第1阶，有1种走法；到达2阶有2种走法；3）利用循环，递推得到后面的结果。

class Solution {
public:
    int climbStairs(int n) {
        vector<int>dp(n+1,0);
        dp[1]=1;
        dp[2]=2;
        for (size_t i=3;i<=n;i++)
            dp[i]=dp[i-1]+dp[i-2];
        return dp[n];
    }
};

从上面的简单的例子可以大致的知道动态规划的原理:

确定原问题与子问题 ：上面的原问题是求n阶台阶的所有走法的数量，子问题就是求1阶台阶，2阶台阶，…，n-1阶调节走法；

确定边界状态：边界状态为1阶与2阶走法，即$dp1=1,dp2=2$;

确定状态转移方程：将求第i个状态的值转化为求第i-1个状态与第i-2个状态的值，动态规划转移方程，$dp[i]=dp[i-1]+dp[i-2] (i>=3)$

例题2、打家劫舍 LeetCode 198

在一条直线上，有n个房屋，每个房屋有数量不等的财宝，有一个盗贼希望从房屋中盗取财宝，但是每个房屋中都有警报器，如果同时从相邻的两个房屋中盗取财宝就会触发警报器，问在不触发警报器的前提下，最多可获得多少财宝。
分析：由于不能同时从相邻的房屋中盗取财宝，因此，
1）若选择第i个房间盗财宝，就一定不能选择第i-1个房屋盗取财宝；
2）若不选择第i个房间盗取财宝，则相当于只考虑前i-1个房间盗取财宝；

确定原问题与子问题 ：上面的原问题是求n个房间的最优解，子问题就是求前1个房间，前2个房间，…，前n-1个房间的最优解；

确定边界状态：边界状态为前1个房间的最优解，即第1个房间的财宝，前2个房间的最优解为前1,2房间中较大财宝;

确定状态转移方程： 1.选择第i个房间：第i个房间财宝+前n-2个房间财宝最优解；2 不选择第i个房间：前n-1个房间的最优解，因此转移方程为： $dp[i]=max(dp[i-1]，dp[i-2]+nums[i]);(i>=3)$

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size()<=0)return 0;
        if(nums.size()==1)return nums[0];
        vector<int>dp(nums.size(),0);
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        for(size_t i=2;i<nums.size();i++)
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        return dp[nums.size()-1];
    }
};

例题3、最大子数组和 LeetCode 53

给定一个数组，q求这个数组的连续子数组中，子数组和的最大值。如数组[-2,1,-3,4,-1,2,1,-5,4],子数组[4,-1,2,1]有最大和sum=6。
分析：将求n个数的数组的最大子数组和，转换为求以第1个，第2个，…，第i个，…，第n个数组结尾的最大子数组和，然后再找出n个结果中最大的，即为结果。
动态规划算法：第i个状态(dp[i])即以第i个数组结尾的最大子数组和。由于以第i-1个数组结尾的最大子数组和$dp[i-1]$与nums[i]相邻：
如果$dp[i-1]>0: dp[i]=dp[i-1]+nums[i]$;否则，dp[i]=nums[i];
参考代码（动规解法）：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
       vector<int>dp(nums.size(),0);
        dp[0]=nums[0];
        int max=dp[0];
        for(int i=1;i<nums.size();i++)
        {
            dp[i]=std::max(dp[i-1]+nums[i],nums[i]);
            if(dp[i]>max)
                max=dp[i];
        }
        return max;
    }
};

非动规解法：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(!nums.size())return 0;
        int max=nums[0];
        int sum=nums[0];
        for(int i=1;i<nums.size();i++)
        {
            sum+=nums[i];
            if(sum<nums[i])sum=nums[i];
            if(sum>max)max=sum;
        }
        return max;
    }
};

例题4、最小路径和 LeetCode 64

给定一个只含非负整数的MN网格，找到一条从左上角到右下角的可以使数字和最小的路径。你在同一时间只能向下或者向右移动一步。
分析：假设矩阵m的大小为MN。先生成大小和m一样的矩阵dp，dp[i][j]表示从左上角走到(i,j)位置的最小路径和。我们可以知道除了第一行和第一列外的其他位置(i,j)，都可以从左边位置(i-1,j)或者上边位置(i,j-1)位置到达(i,j)，所以，其状态方程可以设计为：

$dp[i][j]=min(dp[i-1][j],dp[i][j-1])+m[i][j]$

参考代码：

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size();int n=grid[0].size();
        vector<vector<int>>dp(m,vector<int>(n,0));
        dp[0][0]=grid[0][0];
        for(int i=1;i<m;i++)dp[i][0]=dp[i-1][0]+grid[i][0];
         for(int j=1;j<n;j++)dp[0][j]=dp[0][j-1]+grid[0][j];
         for(int i=1;i<m;i++)
         {
             for(int j=1;j<n;j++)
             {
                 dp[i][j]=std::min(dp[i-1][j],dp[i][j-1])+grid[i][j];
             }
         }
        return dp[m-1][n-1];
    }
};

上面是使用经典的动态规划的方法进行求解，空间复杂度,时间复杂度均是：$O(m*n)$。针对这个问题还可以再上面解法的基础上对空间进行压缩，可以参考这里。

例题5、兑换零钱 LeetCode 322

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。可以认为每种硬币的数量有无限个。
示例1

1
2
3

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

示例2

1 2	Input: coins = [2], amount = 3 Output: -1

对于任意数额，它最后一次加硬币只可能有coins.size()种情况。假设coins=[$c_1$,$c_2$,$c_3$],则，当总金额为11时，有：

$dp[11]=min(dp[11-c_1],dp[11-c_2],dp[11-c_3])+1$

因此我们，用dp[i]表示凑到金额i所需的最小硬币个数，很容易得到转移方程:

$dp[i] = min(dp[i-coins[j]])+1$

参考代码：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) { 
         vector<int> dp(amount+1, INT_MAX); //初始化dp数据都包含int型最大值
        dp[0] = 0;//金额为0时，所需的最小硬币个数为0；
        for (int i=1; i<=amount; i++) {
            for (int j=0; j<coins.size(); j++) {
                if (i-coins[j] >= 0 && dp[i-coins[j]] != INT_MAX) { 
                    dp[i] = min(dp[i], 1+dp[i-coins[j]]);
                }
            }
        }
        return dp[amount]==INT_MAX ? -1 : dp[amount];
    }
};

值得注意的时，上面加了限制条件dp[i-coins[j]] != INT_MAX，是为了避免出现dp[i]加1之后出现溢出的情况。

例题6、换钱方法数 LeetCode 322

给定不同面额的硬币 coins 和一个总金额 amount。求要得到目标金额有多少种不同的硬币组合方式。

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

这道题的解法，其实和上面的那道题题差不多，上面那道题是求$dp[i] = min(dp[i-coins[j]])+1$，而我们这道题目的是求和，$dp[i] = Σdp[i - coins[j]]$,凑成金额为0的方法数只有一种，所以dp[0]=1;一开始我只是简单的将上面那道题改了一下，变成下面这个样子

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) { 
         vector<int> dp(amount+1, INT_MAX-1);
        dp[0] = 1;
        for (int i=1; i<=amount; i++) {
            for (int j=0; j<coins.size(); j++) {
                if (i-coins[j] >= 0) {
                    dp[i] = min(dp[i], 1+dp[i-coins[j]]);
                }
            }
        }
        return dp[amount]==INT_MAX ? -1 : dp[amount];
    }
};

但是，运行结果却是错的，将示例1带入，可以计算出得到，dp5=9,真实的答案是dp[ 5]=4,其实简单的分析就知道$dp5=9$,得到的其实是凑成金额为5的不同面值金额的排列数。这些和方法数是不同的。因此，将上面的循环嵌套顺序换一下，得到下面的代码：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; ++i) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
};

上面的运行结果才是正确的，至于为什么是这样的，我一时也没搞清楚，暂时先放在这里，以后再想吧。这道题还可以参考一下这里。

动态规划也不是一两道题可以讲解清楚的，最重要的还是要自己学会使用动规的思想去解决问题，设计状态转移方程。动态规划目前还在看，后面刷题碰到动态规划的题再来补充。

例题1、 爬楼梯问题 LeetCode 70

例题2、 打家劫舍 LeetCode 198

例题3、 最大子数组和 LeetCode 53

例题4、 最小路径和 LeetCode 64

例题5、 兑换零钱 LeetCode 322

例题6、 换钱方法数 LeetCode 322