推导动态规划问题的公式

  学如逆水行舟，不进则退。当我对算法题的概念还停留在1000题的时候，今天打开力扣一看，已经更新到1900道题了。真的是，没有进步就是在退步。 意识到了算法的重要性，也想通过算法来给自己提升一点自信，又或者说给自己增加一点底气！

  我始终认为，算法题这个东西，它是一个闻道有先后的问题，并不是和智商挂钩的问题。 但是算法也是始终压在我身上的一座大山。翻不过去，我永远都是弟弟。

  最近在摸索一些解题思路，和解题技巧。我会用脑图，加文字，加图片的形式来记录自己的学习和领悟的过程。

正式开始动态规划

先说说为什么是从动态规划开始

  打开力扣刷题网站，选上动态规划标签。光是动态规划问题，就有350道。上边说了，目前力扣上一共也就又1900道。

 所以如果把动态规划问题刷明白了，一下子就会了好多道题。

 每页50道，一共7页，一共350题，都是动态规划的。足矣展示动态规划的重要性了。

动态规划问题语义解析

  从名字中，我们可以得到两个问题。从 “动态” 我们可以推出 “状态”，我也喜欢称作变量。“规划”二字，我们要想到的是“选择”，所谓规划也就是选择最好的结果，也叫做“择优”。

  所以动态规划问题就是在不同的状态中选择出最佳的状态，最终得到问题的解。

动态规划问题思路梳理

   先总结一下动态问题的形态特征。也就是先能辨别到底什么是动态规划问题。或者说，什么时候我去用动态规划来解决问题。

动态规划问题的形态特征

•   动态规划最最最常见的就是求最值问题。最长，最短，最多，最少。

（这是基于我刷题经历来总结，随着题量的增加，会回来补充）

基于现象看本质 - 动态规划的本质是暴力列举所有可能性（穷举）

  那么根据我们上边总出来的动态规划问题的特征，来想一个本质上的问题。

  我先说一个我的认知：计算机是一个非常笨的机器，它没有思维模式的，也不会去主动想问题。那么基于这一点呢，关于最什么什么的问题，计算机只能通过暴露的方式，找到所有的可能性，然后从中对比出最优解。不管是最长还是最短，还是多最少。本质上都一样。

  基于这个本质问题，我们就要养成一个习惯，在看到类似的求最值问题时，首先想的是如何穷举所有的可能性。如果去coding出来所有的可能性。然后再是利用一些技巧去优化我们的算法。

动态规划问题的结构

  我感觉动态固化问题有分治思想在的，就是把大问题化成小问题，最终的求解是在小问题得到解决的基础上的。所以动态规划问题，具备子结构的问题。动态规划要解决的最大的问题，是在暴力穷举过程中，解决重复的子结构问题（子结构第一次出现，在下边的栗子中，会说明什么是子结构）。 所以，它一般情况下，都需要用到一个辅助空间（也可以说是备忘录），来记录这些子问题的解。用专业的术语描述，就是dp数组（dp数组第一次出现，在下边的栗子中，会说明什么是子结构））。

小总结

  到这里，我们应该明白，动态规划问题，实际上就是用一个备忘录，来记录所有可能性的结果。然后暴力穷举所有的结果。最后是在备忘录中找到最好的结果。

动态规划问题细节，抽丝剥茧来解决

  结合上边讲的，我们想要解决一个动态规划问题的时候，要思考两件事：第一件是如何暴力穷举；第二件是如何设计备忘录，也就是 dp数组。

  看似简单就四个字，暴力穷举。但是难就难在了暴力穷举。上边铺垫那么多文字，就是想让大家在心里默默接受暴力穷举这四个字。接下来我们再看看穷举的细节，如何穷举。剩下的就是多看一些题，来找找感觉。

 如何做到动态规划的穷举？

  这是最核心，也是最难的问题。能够解决这个问题，实际上已经完成了百分之八十。穷举，不是你脑补出来所有的可能性，然后从代码一行一行敲出来。那得把我们累死。而是找到状态转移方程。用公式，来描述所有可能性，然后让计算机去完成计算。所以能够否解决问题，在于我们能否写出状态转移方程。

  关于如何写出状态转移方程       

  1. 找到base case。也就是找到最基础的案例。这是一个蛮关键的点，因为递归的时候，它是我们程序的一个退出点。   

  2. 根据上边对动态规划的语义分析，我们要找变化的状态是什么，也就是说都有什么是变量。

  3. 然后是选择，如何去选择最有的状态。前提肯定是列出所有的情况才能找到最有的状态。

 那如何才算列出来所有的情况呢？

  答案是用公式，或者说固定结构。

  再回头看一下我对“动态规划”的语义分析。提到了状态，和变量的问题。来想一下我下边的公式是否合理？ 我下边的公式是否能够列出来所有的情况？ 如有没有问题话，请好好记住这个穷举的公式。 

 for （变量一  in  变量一的所有取值情况 ）{

          for （变量二  in  变量二的所有取值情况） {

                  // TODO something

                  择优

          }

   }

来一个栗子，来验证公式

经典的动态规划问题- 01 背包问题

  来看问题描述：

  给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i]，价值为val[i]，现在让你用这个背包装物品，最多能装的价值是多少？

举个简单的例子，输入如下：

N = 3, W = 4
wt = [2, 1, 3]
val = [4, 2, 3]

算法返回 6，选择前两件物品装进背包，总重量 3 小于W，可以获得最大价值 6。

         

动态规划要解决第一个问题：穷举过程的解题思路

   我们第一步，要找变量是什么，这道题的最关键的点就是找对变量，选对变量。这需要我们去刷非常多的题，来找题感。

  好好的读几遍题，我找到的变量有：

1.  第i个物品的价值 vul[i]
2.  第i个物品的重量 wt[i]
3.  背包可装载重量W

   ok，从三行题上，我们能看出来的变量只有这么多。但是它们都要用做循环体吗？答案是否定的，仔细想一下，上边列出来的第一条变量，以及第二条变量是不是可以合并成第i个我物品？因为前两个变量都属于一个物品的属性。

   所以更新后的变量只有两条：

1. 第i个物品
2. 背包可容量W

   我们已经找到了变量，接着可以套我们的公式了

// 变量一 为第i个物品
for (int i = 1; i