数据结构算法系列----对动态规划的感悟

简介：

      最近我一直在做和复习动态规划的题目，对动态规划有了一些新的理解和感悟。本文就是基于最近做的一些题目写的。

一、动态规划的题目形式和选择

      当题目是对于求某一串数字或者字符的最值时，一般就回想到三种解法，dfs暴搜、动态规划、贪心。在这三个之中显而易见最好想最简单的是dfs，个人认为最难想的是贪心，其实除了少量题目，大部分要用贪心的题目能用贪心也能用动态规划解决，因为dp的规律相对来说是好找的多的。

       当题目是给定定量要你去求这个定量中另一个变量的最大值，其实这种都是背包问题，这种是比较简单的dp直接套模版就好了。

二、动态规划的步骤

        卡哥把动规分为动规五部曲，分别是：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

但是我个人认为其实三部曲就够了，总结成一句话就是定义方程初始化：

      1、确定dp数组含义（最重要）

      2、确定状态转移方程

      3、dp数组初始化

举个例子 leecode：零钱兑换 II 

       很显然这是一个完全背包，但是和模版中状态转移方程式不同

下面这个是模版中的状态转移方程：

dp[j]=max(dp[j]-nums[i],dp[j])

 这个是本题的状态转移方程：

dp[j]+=dp[j-coins[i]];

      为什么会不同，其实是因为dp的含义不一样，模版中的dp是当背包容量为j时最大能装的价值，而本题的是当背包为容量j时有几种方法能装满这个背包。所以因为dp含义的不同状态转移方程也不同。

完整代码：

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