动态规划原理
何为动态规划？
动态规划（\(\text {Dynamic programming}\)），简称 DP。
DP 并不是一种算法，与模拟、贪心一样，而是一种解决问题的方式。
DP 的基本思想为「将给定的问题拆分为一个个规模更小的子问题，直到子问题可以直接解决，返回/保存这个值，再根据方程一步步推出原本问题的答案。」，
有没有发现， DP 定义怎么好像和递归、递推的的差不多？没错，DP 就是基于递归或递推运行的。
DP 的术语：
-
决策，指在问题中可以选择的操作，如在元神中与 \(\texttt {NPC}\) 对话时，你可以选择对话回复的内容。
-
状态，指将原问题划分为更小的子问题时，用来描述子问题的属性或变量的取值。
-
状态空间，指问题中所有可能状态的集合。
DP 的特性为：
- 无后效性，已经求解的子问题，不会再受到后续决策的影响。
- 最优子结构，
DP问题的最优解所包含的子问题的解也是最优的。 - 子任务重叠，有大量重叠的子问题，但是不是所有
DP文问题都有这个特性。
DP 往往用于求最优解问题，例如问题
\(\texttt {Hello Kitty}\) 想搞点花生 \(\texttt {77}\) ，她来到一片有网格道路的 \(r \times c\) 的矩阵花生地，她要从左上角进入，右下角出来。地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，用 \(a_{ij}\) 表示，经过一株花生苗就能摘走该它上面所有的花生。\(\texttt {Hello Kitty}\) 只能向右或向下走，不能向左或向上走。问 \(\texttt {Hello Kitty}\) 最多能够 \(7\) 到多少颗花生。
对于这个问题，DP 时要经过以下三个步骤：
-
确定状态和表达方式，如本题，假设要走到 \((i,j)\) 处，就只能从上面和左边走过来，也就是 \((i - 1,j)\) 和 \((i,j - 1)\) 两种状态，
可以用 \(dp(i,j)\) 来表示从 \((1,1)\) 走到 \((i,j)\) 所能摘到最多的花生数。
-
分解子问题，我们看 \(1.\)，会发现我们可以把 \(dp(r,c)\) 分解成 \(dp(r-1,c),dp(r,c - 1),dp(r - 1,c - 1)\) 三个子问题，
而这些子问题又可以分解为子问题，最后分解为 \(dp(1,1)\)，此时确定边界为 \(dp(1,1) = a_{1,1}\)。
-
列出状态转移方程，状态转移方程就是通过规模更小的子问题推导出本子问题的方程，此题如要推导出 \(dp(i,j)\)，
状态转移方程就是 \(dp(i,j) = \max(dp(i,j - 1),dp(i - 1,j)) + a_{ij}\)。
-
按顺序求解子问题，按照前面想好的，确定
DP顺序（一般自底向上），优化空间（滚动数组），优化时间（记忆化搜索）等。