DP适用

dp一般用于解决多阶段决策问题，即每个阶段都要做一个决策，全部的决策是一个决策序列，要你求一个

所以有多阶段决策类问题，麻烦我脑子能想到 DP算法，而不是傻了吧唧 贪心

最好的决策序列使得这个问题有最优解

！！该问题具有最优子结构。

DP硬核解释

DP的正规解释是：动态规划（英语：Dynamic programming，DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

动态规划问题的三大性质（也是dp能用的三大条件）：

!!1.最优子结构性质：

如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

2.子问题重叠性质：

子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

3.无后效性：

将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

最优子结构?

问题拥有最优子结构：一个问题的最优解可由子问题的最优解有效构造出来。
比如:(采花生, 走到终点或者随便某个点, 它可由左边或者上面的最优解推导而来)。

最优子结构保证了动态规划中原问题的最优解可以由子问题的最优解推导而来。

因此一个问题必须拥有最优子结构，才能用动态规划解决。

DP需要的三要素

• 状态表示
• 状态计算
• 边界

转载+个人理解