动态规划本质动态规划本质就是大问题划分成子问题大问题利用子问题或者子问题之间相互利用从而优化暴力解法。最核心的就是划分子问题而总的来说划分子问题大概可以从两个角度考虑其一就是划分后的子问题和原问题性质一致从子问题开始处理最终解决大的问题层次型划分。通常可以根据某个元素的有无某个元素的个数某几个位置的元素的种类等划分出子问题。还有比较独特的比如“单词拆分”“回文串分割2”这两道题是动态划分子问题在遍历的过程中确定子问题的边界。其二就是后的子问题是原问题的组成部分子问题和原问题的性质不一样组合型划分而这些子问题相互之间有依赖关系。通常可以以某位置为开始或者以某位置为结束或者以i为开始j为结束划分子问题。在子数组系列问题中用处颇多说了这么多其实都可以忘了我们所求的不是固化的解法而是解决问题的思想而动态规划的思想就是大问题划分成子问题大问题利用子问题或者子问题之间相互利用至于如何划分就要我们根据子问题之间的依赖关系灵活决定。什么时候用动态规划通过暴力算法发现有许多的重复计算所以用动态规划或者记忆化搜索来优化解决方案最简单常见问题变化纷杂不知道从何入手这种问题最适合大事化小小事化了的动态规划解法所以不要慌最难的也就是最简单的此时要先找到变化中的不变量然后根据不变量使用动态规划例如编辑距离这道题目先发现了每个单词执行的操作总共就四种然后可以通过这个不变量使用动态规划解决变化纷杂的问题例题这是一道有难度的动态规划题目。看了题目第一时间想到的状态表示就是dp[i][j]在[0-i]之间选k个数乘积的最大值。但是其实题目有诸多限制1.能力可为负数如果只求最大值max但当前选中的数是个负数乘起来反而是最小的了所以取max还是min取决于当前选中的数是正数还是负数。因次最起码我们得有两个dp表一个表示max一个表示min2.距离不超过d这就表明我们只能在有限的范围内去选择依赖dp。3.dp[i][j]是不是还要再多一维表示选不选i位置的数如果不选后面的应该怎么办如果选了又该怎么办这就很复杂了。但我们可以发现我们总是要选一个的因为k1所以不妨假设i位置的数必选我们枚举的是以i位置为结尾的k个数的乘积的最大值。这就容易多了而且如果确定了i位置是被选的那么下一个被选的一定在d范围之内所以我们可以假设下一个数也一定是被选的如果剩余需要的数0逻辑闭环4.细节问题会比较多比如初始化dp明显就不合法的位置如何初始化不需要初始化可以通过限制访问范围来让某位置永远访问不到非法位置。