题目的一般形式

????????求最值，涉及到的方法是穷举。但穷举过程中会存在“重叠子问题”，由此造成穷举效率会很低。“最值”必存在“最优子结构”。但“穷举”并非易事，需要列出“正确的【状态转移方程】”。

????????需要使用【备忘录memoization】或【DP table】来优化穷举过程。这是一种使用空间来换取时间的策略。

题目的典型特点

????????“无后效性”，即：一旦一个子问题的求解得到结果，以后的计算过程就不会修改它。

两种解题思路

? ? ? ? ? ? ? ? ?

“自底而上”的递推，即从基底（base case）出发，根据状态转移方程逐步求出各个状态的解。
“自顶而下”的记忆化递归，即Divide and Conquer。

DP的三要素

重叠的子问题：子问题出现重叠，说明应该用DP
最优子结构：即判断当前节点n的“最值”的比较器。要符合“最优子结构”，子问题间必须相互独立。
状态转移方程：描述问题结构的数学形式。比如，斐波拉奇数列问题中，f(n)是节点n的一个状态，它由状态f(n-1)和状态f(n-2)相加转移得到。（记住这个“状态”的例子，这对找到题目正确的状态，写出状态转移方程至关重要）

DP的难点

? ? ? ? 不知道如何确定【状态】和【选择】，也就找不到正确的【状态转移方程】。

????????【解决方案：通过技巧——数学归纳法】。

原因有二：

? ? ? ? 一是因为穷举需要递归实现
? ? ? ? 二是因为有的问题本身的解空间复杂，不那么容易穷举完整。比如，背包问题、Longest Common Subsequence。

解题策略

? ? ? ? 【状态转移方程】直接代表着暴力解法。千万不要看不起暴力解，只要写出了暴力解，优化方法无非是用备忘录或DP table，其它再无奥妙可言。

? ? ? ? 更具体一点说，找【最优子结构】的过程，其实就是证明状态转移方程正确性的过程，方程符合最优子结构就可以写出暴力解了，写出暴力解就可以看出有没有重叠子问题了。有，则优化；无，则OK。这也是套路，经常刷题的朋友应该能体会。

? ? ? ? 在实际的算法问题中，找到【状态】-->>做出【选择】-->>写出【状态转移方程】是最困难的，这也就是为什么很多朋友觉得动态规划问题困难的原因。

思维框架

????????这里总结了一个思维框架，辅助你思考状态转移方程：

????????“明确 base case ---->>>> 明确【状态】 ---->>>> 明确【选择】 ---->>>> 定义dp 数组/函数的含义”。

? ? ? ? 按上面的套路走，最后的结果就可以套这个框架：

?如何列出正确的状态转移方程？

? ? ? ? 以?LeetCode322零钱兑换问题??和 300最长递增子序列??为例，进行讲解。

明确 base case。这个很简单，显然目标金额amount为0时，算法返回0。因为不需要任何硬币就已经凑出目标金额了。
明确“状态”，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向base case靠近，所以唯一的“状态”就是目标金额amount。? ? ? 而“最长递增子序列”中，“状态”量应该是“以这个数结尾的子序列”。因为在增加元素后的序列中，会变化的变量只有元素数值。
确定“选择”，也就是导致“状态”产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有的硬币的面值，就是你的“选择”。? ? ?而在“最长递增子序列”中，“选择”应该是以这个数结尾的序列中的各个数值对应的最长递增子序列。它的“最优子结构”为前序列的所有“选择”中，以“最接近当前值（必须小于）的数”结尾的最长递增子序列的长度。
明确 dp函数/数组的定义。我们这里讲的是“自顶向下”的解法，所以会有一个递归的dp函数。一般来说，函数的参数就是状态转移中会变化的量，也就是上面说到的“状态”；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即“目标金额”，题目要求我们计算凑出目标金额所需的最少硬币数量。所以，我们可以这样定义dp函数：dp(n)表示，输入一个目标金额n，返回凑出目标金额n所需的最少的硬币数量。? ? ? ? ?而在“最长递增子序列”中，dp(n)应该是以nums[i]这个数结尾的最长递增子序列的长度。