动态规划 (Dynamic Programming,简称 DP)
是一种用于解决多阶段决策问题的数学优化方法。
它通过将原问题分解为相对简单的若干个子问题，并利用状态转移方程来描述子问题之间的递推关系，保存已经解决过的子问题的解，从而避免重复计算，提高了算法效率。
动态规划通常适用于具有重叠子问题和最优子结构性质的问题。
“空间” 换 “时间”
避免重复计算
“带备忘录” 的递归
递归树的剪枝
1.穷举法/暴力搜索
2.记忆化搜索 /剪枝
3.改写成迭代形式
动态规划通常包括以下几个步骤：
- 定义子问题：明确定义子问题，找出子问题之间的关系。
- 构建状态转移方程 ：根据子问题之间的关系，建立递推关系式，描述子问题之间的转移规律。
- 初始化：确定边界条件，即最基本的子问题的解。
- 递推求解：根据状态转移方程，自底向上地求解子问题，直至求解出原问题的解。
动态规划常见的优化方法包括记忆化搜索和状态压缩等。
在实际应用中，动态规划常用于解决最短路径问题、背包问题、序列比对等一系列复杂的优化问题。
动态规划的基本操作：
定义 dp 数组
初始化
转化公式
搞定！
在动态规划算法中，dp[i]通常表示问题的状态或者子问题的解。
具体来说，dp[i]表示解决原问题中规模为i的子问题所需的最优解或者状态值。
在动态规划的求解过程中，通常会定义一个数组dp，用来存储每个子问题的解或状态值。数组的索引i通常代表问题规模或者问题的某个特定状态，dp[i]存储了规模为i的子问题的解。通过填充dp数组并根据状态转移方程逐步更新dp数组中的值，最终可以得到原问题的解。
在动态规划算法中，dp[i]的含义可能会根据具体问题的定义而有所不同，但通常都表示问题的状态或者子问题的解。在实际应用中，理解dp[i]的含义是理解动态规划算法解题思路的关键之一。
题型
线性动态规划：在一个一维数组或字符串上进行状态转移的动态规划问题，比如最长递增子序列、最大子数组和等问题。
矩阵动态规划：在一个二维矩阵上进行状态转移的动态规划问题，比如最大正方形、最大矩形等问题。
背包问题：一种特殊的动态规划问题，通常包括 0-1 背包、完全背包、多重背包等类型。
字符串动态规划：在字符串上进行状态转移的动态规划问题，比如编辑距离、正则表达式匹配等问题。
树形动态规划：在树结构上进行状态转移的动态规划问题，比如树的直径、最大路径和等问题。
区间动态规划：在区间上进行状态转移的动态规划问题，比如区间和、区间乘积最大化等问题。
状态压缩动态规划：一种特殊的动态规划问题，通常用于解决状态空间较大的问题，通过状态压缩来减少状态的数量。
这些是动态规划算法中常见的题型，不同类型的问题需要采用不同的解题思路和技巧。
例题
例题：139
⑥474.一和零
