动态规划（Dynamic Programming）是一种重要算法，通过将原始问题分解成一系列更小的问题，并且通过子问题来避免重复计算，以此来提升时间效率。
动态规划的特性
动态规划、分治、回溯的区别
动态规划是通过将问题分解为子问题来解决问题，但是子问题的分解是一种通用的思路，而动态规划与分治、回溯的侧重点有所不同：
- 动态规划： 动态规划会对问题进行递归分解，但是分解后的子问题直接是相互依赖的，子问题直接会存在推导关系，另外分解过程中也会出现很多相同子问题。
- 分治： 分治算法递归地将原问题划分为多个相互独立的子问题，直至最小子问题，并在回溯中合并子问题的解，最终得到原问题的解。
- 回溯： 回溯会尝试穷举问题的所有解，并通过剪枝来避免不必要的分支。
动态规划常用来求解最优化问题，不仅包含重叠子问题，还有两个特性：最优子结构、无后效性。
最优子结构
原问题的最优解是由子问题的最优解推导
dp[i] = f(dp[i - 1])
无后效性
给定一个确定的状态，当前状态与过去状态无关，当前状态可以推出未来状态
解题思路
如何判断一个问题是否可以由动态规划解决，以及判断后如何入手。
问题判断
如果一个问题包含重叠子问题、最优子结构，并满足无后效性，那么它通常就适合用动态规划求解。但我们很难从问题描述上直接提取出这些特性。所以通常会观察问题是否适合回溯解决。
适合用回溯解决的问题通常满足“决策树模型”，这种问题可以使用树形结构来描述，其中每一个节点代表一个决策，每一条路径代表一个决策序列。
换句话说，如果问题包含明确的决策概念，并且解是通过一系列决策产生的，那么它就满足决策树模型，通常可以使用回溯来解决。
问题判断的加分项：
- 问题包含最优化描述
- 问题状态可使用列表、矩阵、树来表示，状态直接存在推导关系
问题判断的减分项：
- 问题目标是找出所有解
- 问题描述有明显的排列组合特征
问题求解步骤
大概流程为：描述决策，定义状态，建立 dp 表，推导状态转移方程，确定边界条件等。
0-1 背包问题
背包问题是一个非常好的动态规划入门题目，是动态规划中最常见的问题形式。
0-1 背包问题： 给定 n 个物品，第 𝑖 个物品的重量为 wgt[i−1]、价值为 val[i−1]，和一个容量为 c 的背包。每个物品只能选择一次，求出在不超过背包容量下能放入物品的最大价值。
将 0‑1 背包问题看作是一个由 n 轮决策组成的过程，每个物体都有不放入和放入两种决策，因此该问题是满足决策树模型的。该问题的目标是求解“在限定背包容量下的最大价值”，因此较大概率是个动态规划问题。
解题思路
描述决策： 对于每个物品来说，不放入背包，背包容量不变；放入背包，背包容量减小。
定义状态： 前 i 个物品在剩余容量为 𝑐 的背包中的最大价值，记为 dp[i, c]。
建立 dp 表： 根据上一步建立 (n + 1) * (c + 1) 的二维 dp 表。
推导状态转移方程：
当我们做出物品 𝑖 的决策后，剩余的是前 i−1 个物品的决策，可分为以下两种情况。- 不放入物品 i：背包容量不变，状态变化为 [i−1, c]。
- 放入物品 i：背包容量减小 wgt[i−1]，价值增加 val[𝑖−1]，状态变化为[i−1, c−wgt[i−1]]。
最大价值 dp[i, c] 等于不放入物品 i 和放入物品 i 两种方案中的价值更大的那一个。
- 确定边界条件：当无物品或无剩余背包容量时最大价值为 0。
完全背包问题
完全背包问题： 给定 n 个物品，第 i 个物品的重量为 wgt[i−1]、价值为 val[i−1]，和一个容量为 c 的背包。每个物品可以重复选取，问在不超过背包容量下能放入物品的最大价值。
完全背包和 0‑1 背包问题非常相似，区别仅在于不限制物品的选择次数，在选择物品 i 之后，仍可以选择物品 i。
在完全背包问题中，状态 [i, c] 为：
- 不放入物品 i ：与 0‑1 背包相同，转移至[i−1, c]。
- 放入物品 i ：与 0‑1 背包不同，转移至[i, c−wgt[i−1]]。
零钱兑换问题
零钱兑换问题： 给定 n 种硬币，第 𝑖 种硬币的面值为 coins[𝑖−1]，目标金额为 amt，每种硬币可以重复选取，问能够凑出目标金额的最少硬币个数。如果无法凑出目标金额则返回 −1。
零钱兑换问题是完全背包问题的一种特例，背包问题是要最大化物品价值，零钱兑换问题是要最小化硬币数量；背包问题是求不超过背包容量下的解，零钱兑换是求恰好凑到目标金额的解。
在状态转移过程中，要求目标金额的最少硬币数，因此是要求最小值。
在确定边界条件时，无法凑出目标金额时，即为无解，返回 -1。
零钱兑换问题 Ⅱ
零钱兑换问题 Ⅱ： 给定 n 种硬币，第 𝑖 种硬币的面值为 coins[i−1]，目标金额为 amt，每种硬币可以重复选取，问在凑出目标金额的硬币组合数量。
定义状态时，子问题应该为前 i 种硬币能够凑出金额 a 的组合数量。当前状态的组合数量等于不选当前硬币与选当前硬币这两种决策的组合数量之和。
总结
- 所有动态规划都可以使用回溯算法解决，但在回溯算法的递归树中存在大量的重叠子问题，效率极低。通过引入记忆化列表，可以存储所有计算过的子问题的解，从而保证重叠子问题只被计算一次。
- 记忆化递归是一种从顶至底的递归式解法，而与之对应的动态规划是一种从底至顶的递推式解法。