动态规划

简要理解

动态规划的思想是把问题划分为多个子问题，但子问题常常并不是互相独立的，当前子问题的解可看作是前面多个阶段的完整总结，所以它需要在子问题求解过程中进行多次判断与选择，与前面的问题相比，它现阶段一定要构成一种最优的结构，它满足最优化原理， 最优化原理：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。同时，这样的最优策略是针对有已作出决策的总结，对后来的决策没有直接影响，只能借用目前最优策略的状态数据。这也被称之为无后效性。 ### 求解思路开始先要将问题按照一定顺序划分为各个阶段，然后确定每个阶段的状态，然后重点是根据决策的方法来确定状态转移方法，也就是说根据当前的状态确定下一阶段的状态，在这个过程中，下一状态的确定往往要参考之前的状态，因此需要在每一次状态转移过程中将当前的状态遍历记录，方便之后的查找。 ### 算法特点 * 需要在给定约束条件下优化某种指标时，动态规划是很有用的 * 问题可以分解为离散子问题是，可以用动态规划来解决 * 没有通用固定的公式，需要具体问题具体分析，这也就是其难点所在

经典示例

背包问题：如果有一个小偷背有一个容量为4kg的背包去商场偷东西，可盗窃的物品有如下三件：音响：3000 4kg 笔记本：2000 3kg 吉他：1500 1kg 每个物品只能偷一次，请问，小偷怎么偷收益最高 解决方法 我们可以考虑用画网格的方法来解决，我们构造下面的网格，每一行代表新添加的可以拿到物品，每一列代表当前容量，数字代表当前情况下可以拿的最大收益。这个过程就是动态规划的经典应用过程，就是保存上一步的结果，在这层进行决策时，与上一层结果比较，得到最优解示意图如下：

最长公共子串问题 如果用户在字典网站中查找单词时不小心拼错了，你必须猜测她原本要输入什么单词，例如啊彬想查单词fish，但不小心输入了hish，在网站的字典中，根本就没有这样的单词，但有类似的单词，那我们如何做这个判断呢？同样的，我们也可以构建一个网格，上方是输入单词的每个字母，左边是待匹配单词的字母，如果匹配就是左上角数字+1，最后比较整个方格中的最大值谁大，最大的就最匹配。示意图如下：

总结从上面的两个例子可以看出，动态规划的核心是对上一步操作进行记忆，再与现在的操作进行对比，已得到最优解，同时，我们可以发现，不同问题中的动态规划虽然思路大体一致，都是保存上一步解并在确定这一步解时做参考，但具体实现上是完全不同的，所以说动态规划题并没有通用解法