1. 动态规划复习小结

   最早系统的学习动态规划还是在大二算法课上，当时因为仓促应付考试的原因，学的也是一些皮毛，并没有真正理解动态规划的精髓所在。后来才发现，动态规划在算法方面的应用实在是太多了，很多hard题目都是动态规划相关。动态规划非常的灵活，可以说没有任何套路可循。给你一个动态规划的问题，能否很好的解决出来真的就是靠感觉和经验。

   在最近做leetcode期间，我再一次被动态规划相关问题所困扰。因此便想好好联系一下相关题目，同时也找了很多网上的教程学习参考。在此对这一阶段学习的内容做一个小小的复习。

   动态规划问题的特点

   我们在解决问题的时候，很少会告诉你这就是一个动态规划的问题，更多的是直接让你去解决。那么如何去判断一个问题是不是动态规划问题呢？

   其实也很简单，动态规划的目的，或者说作用就是用已有结果计算当前问题，已达到避免重复计算的目的。在做了一些题目以后发现，动态规划问题一般都是求最值的问题。当你拿到一个问题后，可以先尝试着用暴力方法来解决这个问题，找到问题的暴力解之后， 仔细分析这个解法，如果出现了很多重复计算的子问题，并且子问题之间互不相关，那么这就是动态规划的问题了。再者，还有一个办法就是对于原问题dp[i] [j]，有不止一条路径可以到达dp[i-1] [j-1]，一旦有一条路径是重复的，就是说明存在重复的子问题了，也就是说这是一个动态规划的问题了。

   最优子结构

   刚才提到的很多重复计算的子问题，也不是所有的这样的情况都是动态规划问题。动态规划中提到的子问题称为 最优子结构 ,其实就是子问题之间只要没有直接关联，不会相互影响就是最优子结构，只要带入几个具体实例尝试一下便知道了。
   但是不是所有问题都会有最优子结构，这不是说这个问题就一定不能用动态规划的思路来解决，而是需要对子问题进行优化和等价转化。通过将不是最优子结构的问题转化为另一个等价的问题来构造最优子结构

   基本框架

   虽然说动态规划问题非常灵活，这是指动态规划问题的dp table的设计非常灵活，但是总的解决问题的方向还是有的。在参考了很多思想之后，我发现了一种理解起来比较好的解决问题的思路。

   首先明确一个概念：动态规划的核心还是穷举。其实在计算机中，所有的解决问题的方法都是穷举，只是问题的关键在于如何更加聪明的穷举，这是很多算法研究的方向。在动态规划中，穷举是通过dp table+状态转移方程 完成的。在动态规划的问题中，这两点各占问题的50%。

   如果要将动态规划问题的解决路线模式化，我认为如下模式比较合适：

   1. 明确问题的状态
   2. 确定dp tatble的含义
   3. 明确当前的选择
   4. 写出状态转移方程
   5. 初始化base case

   1. 明确问题的状态

   何为问题的状态？这个定义很抽象。状态就是问题中的变化的量，或者可以类比为自动机中的状态的感觉。

   2. 确定dp table的含义

   dp table是解决动态规划问题的两个关键之一。dp table通常是一维，二维数组或者一个字典。关于如何定义dp table，我认为没有什么技巧，只能通过不断的积累经验。下面记录几个最近常用的定义方式（后面不断补充）：

   • 字符串相关的问题：
     一般是定义一个二维数组，dp[i][j] 为s1[0…i] 到s2[0…j]的最大值（示具体情况而定）
     定义完dp table，动态规划问题就解决了一半，最终答案一般为dp[n]。

   3.明确当前选择

   什么又是选择？选择是在当前状态下，可以做出的改变，是状态转移方程的基础。动态规划问题就是在当前状态下，在可选的选择中择优选择。越来越发现动态规划问题和有限状态机有一定的相似之处：
   这个图明确了状态和选择之间的关系，状态转移方程只不过是将这个图用数学方式描述出来，仅此而已。

   4.写出状态转移方程

   有了上面的工作做铺垫，写出状态方程则是水到渠成的事情。其实前面4步没有特别严格的顺序。通常情况下不能直接看出问题的状态转移方程，可以先写出问题的暴力解法，然后一步步的从中分析出问题的状态方程。
   另一个角度，在定义了dp table后，可以考虑一下如何推导出dp[i] [j]，这也就是状态转移方程的另一种表现形式，也就是数学归纳法。

   5. 初始化base case

   可以说这一步是整个动态规划解题过程中最简单的一步了，但也是同样重要的一步。这一步只需要根据dp table的定义，确定base case即可

   一些注意事项

   dp数组的遍历顺序问题

   如何遍历一个dp数组？到底是正着遍历还是反着遍历？其实只要遵循一个原则：只要能够从base case根据状态转移方程推导到最终答案即可。
   再次记录一下斜着遍历数组的实现：

   for p in range(m):
       for q in range(n-i):
           i = q
           j = p+q
           dp[i][j] = ...

   目前我对动态规划的理解就是这样一个程度，后续随着不断的学习会继续补充，也会选择几个个人非常喜欢和经典的题目进行解析。