动态规划套路

到底怎么学动态规划？

回想起当初学动态规划的时候，是真的难。动态规划的确很难，很考验逻辑思维能力、抽象能力、还有数学建模能力。但是入门动态规划真的有这么难吗？我觉的其实真的不难，就是单纯的找规律；这里我想以一种比较野路子的方式帮助大家入门理解动态规划，这种方法真的是很简单且有效果，大神请忽略。

DP table

什么方法呢？直接画表格，找规律。这个办法在很多题目下都是非常的有效果，特别是矩阵型dp，简直是万金油；这种方法非常简单，你只需要记住两个技巧。

把问题的规模变小，变成小问题思考
根据小问题来填表格，找出规律

记住这两个技巧，下面我以一道相对简单，一道稍微难一点的真题还讲解。

62.不同路径

首先分析一下题目，题目说机器人只能往下，或者往右走，到达右下角有多少种走法。

不要单纯的干想，单纯的干想会浪费很多的时间，甚至手足无措，完全不知道怎么办了，直接画表格找规律，这里我以一个5*7的表格来举例。

首先为什么第一行第一列全是1？因为如果只有第一行第一列，机器人就只有一条路可走。
回忆一下上面两个技巧；假设我们把网格变小，也就是把问题的规模变小，变成一个3*3的表格。
3*3 有多少种走法很简单吧？直接把表格填完就可以得到答案了，答案就是6种。
为什么是6种呢？因为机器人只能往右或者往下走，到达3 * 3的最右下角，只能往上面下来，或者左边过来。
那如果把问题的规模继续变大，变成4*4的表格呢？我们继续填表

继续观察答案，答案是20种；那有什么规律呢？我相信没有人会发现不了这个规律吧？
很明显，table[3][3] = table[2][3] + table[3][2]，也就是说机器人走到规模为4 * 4的网格右下角有20种走法。

书写代码

到这里，我相信写出代码应该不难了吧？

var uniquePaths = function (m, n) {
  // 因为第一行第一列都是1
  let dp = Array.from(new Array(m), () => new Array(n).fill(1))
  for(let i = 1; i < m; i++){
    for(let j = 1; j < n; j++){
      // 当前的等于上面的（dp[i - 1][j]）+ 左边的（dp[i][j - 1]）
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    } 
  }
  return dp[m - 1][n - 1]
};

其实动态规划也就这么简单，就是单纯的画表格找规律。

1143.最长公共子序列

分析下题目，要找两个串的最长公共子序列，不要多想。直接画表格观察规律

为什么会有空串？为什么空串对应的都是0？你想呀，需要从无到有推导出答案，找出规律，所以需要借助空串；如果两个串中的其中一个为空，那肯定都是0呀。
因为用例的答案是3，所有我先把结果先上去，好利用这个结果来找出规律。
我们继续填表推导，找出规律。

当问题的规模变大，text1[0] == text2[0]，答案很明显是1。这里我们就发现了相等的时候要加1了，好家伙，继续观察。

为什么我会先填 text1[0] == text2[0] 对应的行和列呢？因为当text1/text2的长度继续变长的时候，最终的结果会受影响吗？很明显，不受影响，继续填表找规律。

当我们填到text1[i] == text2[j]，也就是c字符相等的时候，由之前找到的规律，它一定要加1，但是在哪个基础上加1呢？很明显是问题的规模变小的时候，也就是没有c这个字符的时候，也就是表格的table[1][2]，绿色区域为1的块。
继续以这个规律填表格看看，我们看红色块。

最终验证了答案，当两个字符相等的时候，就等于上一个规模小的问题加1，不想等的就相当于有没有这个字符都一样。取两个串少一个的情况下的最大值就可以了。
所以规律如下：

text1[i] == text2[j], table[i][j] = table[i - 1][j - 1] + 1
text1[i] != text2[j], table[i][j] = max(table[i - 1][j], table[i][j - 1])

书写代码

var longestCommonSubsequence = function(text1, text2) {
  let n = text1.length
  let m = text2.length
  let dp = Array.from(Array(n + 1), () => Array(m + 1).fill(0))
  //空串都是0，0不用看了   
  for(let i = 1; i <= n; i++){
    for(let j = 1; j <= m; j++){
      if(text2[j - 1] == text1[i - 1]){
         dp[i][j] = dp[i - 1][j - 1] + 1
      }else{
         dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
      }
    }
  }
  return dp[n][m]
};

总结

其实这种办法写动态规划是非常野路子的，但是对于新手来说，入门确实不错。动态规划确实有点难，把它讲明白，讲清楚也不简单，希望我这篇水文能帮助你更好的理解动态规划吧。互联网人共勉~