背景
一般形式是求最值，核心是穷举。
首先，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，需要你熟练掌握递归思维，只有列出正确的「状态转移方程」，才能正确地穷举。而且，你需要判断算法问题是否具备「最优子结构」，是否能够通过子问题的最值得到原问题的最值。另外，动态规划问题存在「重叠子问题」，如果暴力穷举的话效率会很低，所以需要你使用「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。
以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。具体什么意思等会会举例详解，但是在实际的算法问题中，写出状态转移方程是最困难的，这也就是为什么很多朋友觉得动态规划问题困难的原因。以下是总结的一个思维框架，辅助思考状态转移方程：
明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 `dp` 数组/函数的含义
下面会举两道题目的例子进行解释。
509. 斐波那契数
https://leetcode.cn/problems/fibonacci-number/description
暴力递归
//最简单递归
int fib(int N) {
if (N == 1 || N == 2) return 1;
return fib(N - 1) + fib(N - 2);
}低效的原因：
存在大量重复计算，比如 `f(18)` 被计算了两次，而且你可以看到，以 `f(18)` 为根的这个递归树体量巨大，多算一遍，会耗费巨大的时间。更何况，还不止 `f(18)` 这一个节点被重复计算，所以这个算法及其低效。
这就是动态规划问题的第一个性质：重叠子问题。下面，我们想办法解决这个问题。
带备忘录的递归解法
int fib(int N) {
//初始化备忘录全为0
int[] memo = new int[N + 1];
return dp(memo[], N);
}
//带着备忘录进行递归
int dp(int[] memo, int n) {
//base case
if (n == 0 || n == 1) {
return n;
}
if (memo[n] != 0) {
return memo[n];
}
memo[n] = dp(memo, n - 1) + dp(memo, n - 2);
return memo[n];
}
实际上，带[备忘录]的递归算法，把一棵存在巨量几余的递归树通过[剪枝]，改造成了一幅不存在几余的递归图，极大减少了子问题 (即递归图中节点)的个数。
子问题个数，即图中节点的总数，由于本算法不存在冗余计算，子问题就是 `f(1)`, `f(2)`, `f(3)` ... `f(20)`，数量和输入规模 n = 20 成正比，所以子问题个数为 O(n)。解决一个子问题的时间，同上，没有什么循环，时间为 O(1)。
所以，本算法的时间复杂度是 O(n)，比起暴力算法，是降维打击。
啥叫「自顶向下」？注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从一个规模较大的原问题比如说 `f(20)`，向下逐渐分解规模，直到 `f(1)` 和 `f(2)` 这两个 base case，然后逐层返回答案，这就叫「自顶向下」。
啥叫「自底向上」？反过来，我们直接从最底下、最简单、问题规模最小、已知结果的 `f(1)` 和 `f(2)`（base case）开始往上推，直到推到我们想要的答案 `f(20)`。这就是「递推」的思路，这也是动态规划一般都脱离了递归，而是由循环迭代完成计算的原因。
//这种是从底向上算的版本
int fib(int N) {
if (N == 0) return 0;
int[] dp = new int[N + 1];
// base case
dp[0] = 0; dp[1] = 1;
// 状态转移
for (int i = 2; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[N];
}所以说自顶向下、自底向上两种解法本质其实是差不多的，大部分情况下，效率也基本相同。
这里，引出「状态转移方程」这个名词，实际上就是描述问题结构的数学形式：
为啥叫「状态转移方程」？其实就是为了听起来高端。
`f(n)` 的函数参数会不断变化，所以你把参数 `n` 想做一个状态，这个状态 `n` 是由状态 `n - 1` 和状态 `n - 2` 转移（相加）而来，这就叫状态转移，仅此而已。
你会发现，上面的几种解法中的所有操作，例如 `return f(n - 1) + f(n - 2)`，`dp[i] = dp[i - 1] + dp[i - 2]`，以及对备忘录或 DP table 的初始化操作，都是围绕这个方程式的不同表现形式。
可见列出「状态转移方程」的重要性，它是解决问题的核心，而且很容易发现，其实状态转移方程直接代表着暴力解法。
千万不要看不起暴力解，动态规划问题最困难的就是写出这个暴力解，即状态转移方程。
只要写出暴力解，优化方法无非是用备忘录或者 DP table，再无奥妙可言。
322. 零钱兑换
https://leetcode.cn/problems/coin-change/description/
暴力递归
首先，这个问题是动态规划问题，因为它具有「最优子结构」的。要符合「最优子结构」，子问题间必须互相独立。啥叫相互独立？你肯定不想看数学证明，我用一个直观的例子来讲解。
回到凑零钱问题，为什么说它符合最优子结构呢？假设你有面值为 `1, 2, 5` 的硬币，你想求 `amount = 11` 时的最少硬币数（原问题），如果你知道凑出 `amount = 10, 9, 6` 的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为 `1, 2, 5` 的硬币），求个最小值，就是原问题的答案。因为硬币的数量是没有限制的，所以子问题之间没有相互制，是互相独立的。
所以我们可以这样定义 `dp` 函数：`dp(n)` 表示，输入一个目标金额 `n`，返回凑出目标金额 `n` 所需的最少硬币数量。
👆想明白这个点之后就可以写伪代码了！！
// 伪码框架
int coinChange(int[] coins, int amount) {
// 题目要求的最终结果是 dp(amount)
return dp(coins, amount)
}
// 定义：要凑出金额 n，至少要 dp(coins, n) 个硬币
int dp(int[] coins, int n) {
// 做选择，选择需要硬币最少的那个结果
for (int coin : coins) {
res = min(res, 1 + dp(coins, n - coin))
}
return res
}再往上加入base case 搞定，这题环境下的base case是，当n<0时返回-1，=0时返回0（也就是结束递归的情况。
int coinChange(int[] coins, int amount) {
// 题目要求的最终结果是 dp(amount)
return dp(coins, amount)
}
// 定义：要凑出金额 n，至少要 dp(coins, n) 个硬币
int dp(int[] coins, int amount) {
// base case
if (amount == 0) return 0;
if (amount < 0) return -1;
int res = Integer.MAX_VALUE;
for (int coin : coins) {
// 计算子问题的结果
int subProblem = dp(coins, amount - coin);
// 子问题无解则跳过
if (subProblem == -1) continue;
// 在子问题中选择最优解，然后加一
res = Math.min(res, subProblem + 1);
}
return res == Integer.MAX_VALUE ? -1 : res;
}
递归算法的时间复杂度分析：子问题总数 x 解决每个子问题所需的时间。文章来源：https://www.toymoban.com/news/detail-792394.html
带备忘录的递归
类似之前斐波那契数列的例子，只需要稍加修改，就可以通过备忘录消除子问题：文章来源地址https://www.toymoban.com/news/detail-792394.html
class Solution {
int[] memo;
int coinChange(int[] coins, int amount) {
memo = new int[amount + 1];
// 备忘录初始化为一个不会被取到的特殊值，代表还未被计算
Arrays.fill(memo, -666);
return dp(coins, amount);
}
int dp(int[] coins, int amount) {
if (amount == 0) return 0;
if (amount < 0) return -1;
// 查备忘录，防止重复计算
if (memo[amount] != -666)
return memo[amount];
int res = Integer.MAX_VALUE;
for (int coin : coins) {
// 计算子问题的结果
int subProblem = dp(coins, amount - coin);
// 子问题无解则跳过
if (subProblem == -1) continue;
// 在子问题中选择最优解，然后加一
res = Math.min(res, subProblem + 1);
}
// 把计算结果存入备忘录
memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
return memo[amount];
}
}到了这里，关于动态规划学习笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
