《刷题健身两不误》龙傲天转世

23、8.31 动态规划开

　　动态规划解题套路框架：
　　322. 零钱兑换
　　凑零钱的问题，展示了如何流程化确定「状态转移方程」，只要通过状态转移方程写出暴力递归解，剩下的也就是优化递归树，消除重叠子问题而已。

　　如何列出正确的状态转移方程？
　　1、确定 base case，这个很简单，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何面值就已经凑出目标金额了。
　　2、确定「状态」，也就是原问题和子问题中会变化的变量。由于数量无限，价值的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。
　　3、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择面值的时候，你每选择一枚面值金额，就相当于减少了目标金额。所以说所有存在的面值，就是你的「选择」。
　　4、明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少数额的数量。所以我们可以这样定义 dp 函数：
　　dp(n) 的定义：输入一个目标金额 n，返回凑出目标金额 n 的最少所需要的数量。

　　509. 斐波那契数 这个倒是简单，直接公式套入。自底向上的递归算法。可以从这题看出动态规划的本质，就是在保证每一个数都能算出来的同时，还可以减少冗余。

　　动态规划设计：最长递增子序列：
　　300. 最长递增子序列
　　注意「子序列」和「子串」这两个名词的区别，子串一定是连续的，而子序列不一定是连续的。

　　今天高度专注，头就开始疼，又有点想yue，晚上看看八股得了
　　希望明天不要出现这种状况，真的难受