最小路径和
暴力解法
备忘录 递归解法
dp数组 迭代解法
魔塔通关
上文 最小路径和 类似，问你从左上角到右下角的最小路径和是多少。感觉这道题和最小路径和有点关系对吧？
- 想要最小化骑士的初始生命值，是不是意味着要最大化骑士行进路线上的血瓶？是不是相当于求「最大路径和」？是不是可以直接套用计算「最小路径和」的思路？
但是稍加思考，发现这个推论并不成立，吃到最多的血瓶，并不一定就能获得最小的初始生命值。
<br />**所以，关键不在于吃最多的血瓶，而是在于如何损失最少的生命值。**
- 不合适的dp函数 定义 ： 从左上角（grid[0][0]）走到grid[i][j]至少需要dp(grid, i, j)的生命值。
- 具体来说，「到达A的最小生命值」应该能由「到达B的最小生命值」和「到达C的最小生命值」推导出来
但问题是，能推出来么？实际上是不能的。因为按照dp函数的定义，你只知道「能够从左上角到达B的最小生命值」，但并不知道「到达B时的生命值」。
- 正确的dp函数 定义：从grid[i][j]到达终点（右下角）所需的最少生命值是dp(grid, i, j)。
（这时候，B、C这个位置 最少需要多少血 是知道的）
那么怎么推出dp(0, 0)是多少呢？
- 假设A的值为 1，既然知道下一步要往C走，且dp(1, 0) = 4意味着走到grid[1][0]的时候至少要有 4 点生命值，那么就可以确定骑士出现在A点时需要 4 - 1 = 3 点初始生命值，对吧。
- 那如果A的值为 10，落地就能捡到一个大血瓶，超出了后续需求，4 - 10 = -6 意味着骑士的初始生命值为负数，这显然不可以，骑士的生命值小于 1 就挂了，所以这种情况下骑士的初始生命值应该是 1。
综上，状态转移方程已经推出来了：
- 自顶向下带备忘录的动态规划解法
圆盘输入字符串
原题可以转化为：圆盘固定，我们可以拨动指针；现在需要我们拨动指针并按下按钮，以最少的操作次数输入key对应的字符串。
1. 状态、选择
1）「状态」就是「当前需要输入的字符」和「当前圆盘指针的位置」
- 这个dp函数的定义如下：当圆盘指针指向ring[i]时，输入字符串key[j..]至少需要dp(ring, i, key, j)次操作。
2）「选择」就是「如何拨动指针得到待输入的字符」
- 再具体点就是，对于现在想输入的字符key[j]，我们可以如何拨动圆盘，得到这个字符？
比如说输入ring = “gdonidg”，现在圆盘的状态如下图：
假设我想输入的字符key[j] = “d”，圆盘中有两个字母”d”，而且我可以顺/逆时针拨动指针，所以总共有四种「选择」输入字符”d”，我们需要选择操作次数最少的那个拨法。
至于到底是顺时针还是逆时针，其实非常好判断，怎么近就怎么来；但是对于圆盘中的两个字符”d”，还能是怎么近怎么来吗？
- 不能，因为这和key[i]之后需要输入的字符有关，还是上面的例子：
- 如果输入的是key = “di”，那么即便右边的”d”离得近，也应该去左边的”d”，因为左边的”d”旁边就是”i”，「整体」的操作数最少。
那么，应该如何判断呢？
- 穷举，递归调用dp函数，把两种选择的「整体」代价算出来，然后再做比较就行了。
完整代码：
加权最短路径
加权有向图中求最短路径的问题
- 说白了，就是给你一幅加权有向图，让你求src到dst权重最小的一条路径，同时要满足，这条路径最多不能超过K + 1条边（经过K个节点相当于经过K + 1条边。
思路一：BFS算法路径
思路二：动态规划思路
先不管K的限制，单就「加权最短路径」这个问题来看，它怎么是个动态规划问题了呢？
比方说，现在我想计算src到dst的最短路径。但我不知道最小权重是多少，但我可以把问题分解成：
s1, s2是指向dst的相邻节点，它们之间的权重我是知道的，分别是w1, w2。只要我知道了从src到s1, s2的最短路径，我不就知道src到dst的最短路径了吗！
别忘了，题目对最短路径还有个「路径上不能超过K + 1条边」的限制。
那么我们不妨定义这样一个dp函数：int dp(int s, int k);
- 函数的定义如下：从起点src出发，k步之内（一步就是一条边）到达节点s的最小路径权重为dp(s, k)。
函数的base case
题目想求的最小机票开销就可以用dp(dst, K+1)来表示
添加了一个K条边的限制，状态转移方程怎么写呢？其实和刚才是一样的：
K步之内从src到dst的最小路径权重是多少？我不知道。但我可以把问题分解：
s1, s2是指向dst的相邻节点，我只要能够在K - 1步之内从src到达s1, s2，那我就可以在K步之内从src到达dst。也就是如下关系式：
我怎么知道s1, s2是指向dst的相邻节点，他们之间的权重是w1, w2？
我希望给一个节点，就能知道有谁指向这个节点，还知道它们之间的权重，对吧。专业点说，得用一个数据结构记录每个节点的「入度」indegree
代码实现
有了indegree存储入度，那么就可以具体实现dp函数了：
备忘录消除 重叠子问题
正则表达式
思路分析
正则表达算法：只需要把住一个基本点：看两个字符是否匹配，一切逻辑围绕匹配/不匹配两种情况展开。
- 如果不考虑*通配符，面对两个待匹配字符s[i]和p[j]，我们唯一能做的就是看他俩是否匹配：
- 那么考虑一下，如果加入*通配符，局面就会稍微复杂一些，不过只要分情况来分析
- 当p[j + 1]为*通配符时，我们分情况讨论下：
动态规划详解
- 选择、状态
- dp函数的定义
- base case
- 哈希表备忘录解决重叠子问题
高楼扔鸡蛋（普通版）
也就是让你找摔不碎鸡蛋的最高楼层F，但什么叫「最坏情况」下「至少」要扔几次呢？
- 最坏情况：最坏情况应该是试到第 7 层鸡蛋还没碎（F = 7），或者鸡蛋一直碎到第 1 层（F = 0）。
- 至少：二分法/线性查找
思路分析
- 状态、选择
- 「状态」很明显，就是当前拥有的鸡蛋数K和需要测试的楼层数N。
- 「选择」其实就是去选择哪层楼扔鸡蛋。
- 状态转移
- 如果鸡蛋碎了，那么鸡蛋的个数K应该减一，搜索的楼层区间应该从[1..N]变为[1..i-1]共i-1层楼；
- 如果鸡蛋没碎，那么鸡蛋的个数K不变，搜索的楼层区间应该从 [1..N]变为[i+1..N]共N-i层楼。
- base case
- 备忘录
- 代码中为什么用一个 for 循环遍历楼层[1..N]，也许会把这个逻辑和之前探讨的线性扫描混为一谈。其实不是的，这只是在做一次「选择」。
- 比方说你有 2 个鸡蛋，面对 10 层楼，你得拿一个鸡蛋去某一层楼扔对吧？那选择去哪一层楼扔呢？不知道，那就把这 10 层楼全试一遍。至于鸡蛋碎没碎，下次怎么选择不用你操心，有正确的状态转移，递归会算出每个选择的代价，我们取最优的那个就是最优解。
- 其实，这个问题还有更好的解法，比如修改代码中的 for 循环为二分搜索，可以将时间复杂度降为 O(KNlogN)；再改进动态规划解法可以进一步降为 O(KN)；使用数学方法解决，时间复杂度达到最优 O(K*logN)，空间复杂度达到 O(1)。
高楼扔鸡蛋（进阶）
1. 二分搜索优化
回顾这两个dp函数的曲线，我们要找的最低点其实就是这种情况：
熟悉二分搜索的同学肯定敏感地想到了，这不就是相当于求 Valley（山谷）值嘛，可以用二分查找来快速寻找这个点的，直接看代码吧，整体的思路还是一样，只是加快了搜索速度：
2. 重写 状态转移
之前的dp数组定义：dp[k][n] = m
# 当前状态为 k 个鸡蛋，面对 n 层楼
# 这个状态下最少的扔鸡蛋次数为 m最终我们想要的答案就是dp(K, N)的结果。 这种思路下，肯定要穷举所有可能的扔法的，用二分搜索优化也只是做了「剪枝」，减小了搜索空间，但本质思路没有变，只不过是更聪明的穷举。
新的dp数组定义：dp[k][m] = n
# 当前有 k 个鸡蛋，允许尝试扔 m 次鸡蛋
# 这个状态下，最坏情况下最多能确切测试一栋 n 层的楼
# 使得你可以确定楼层 F 使得鸡蛋恰好摔不碎
# （一层一层线性探查嘛）
这其实是原思路的一个「反向」版本，先不管这种思路的状态转移怎么写，来思考一下这种定义之下，最终想求的答案是什么？
- 我们最终要求的其实是扔鸡蛋次数m，但是这时候m在状态之中而不是dp数组的结果，可以这样处理：
原始解法还得线性/二分扫描所有楼层，求最大/小值。但现在这种dp定义不需要这些了，基于下面两个事实：
1、无论你在哪层楼扔鸡蛋，鸡蛋只可能摔碎或者没摔碎，碎了的话就测楼下，没碎的话就测楼上。
2、无论你上楼还是下楼，总的楼层数 = 楼上的楼层数 + 楼下的楼层数 + 1（当前这层楼）。
根据这个特点，可以写出下面的状态转移方程：dp[k][m] = dp[k][m-1] + dp[k-1][m-1] + 1
- dp[k][m - 1]就是楼上的楼层数，因为鸡蛋个数k不变，也就是鸡蛋没碎，扔鸡蛋次数m减一；
- dp[k - 1][m - 1]就是楼下的楼层数，因为鸡蛋个数k减一，也就是鸡蛋碎了，同时扔鸡蛋次数m减一。
PS：这个m为什么要减一而不是加一？之前定义得很清楚，这个m是一个允许的次数上界，而不是扔了几次。
如果你还觉得这段代码有点难以理解，其实它就等同于这样写：
- 要求的不是dp数组里的值，而是某个符合条件的索引m，所以用while循环来找到这个m而已。
3. 数学方法
戳气球问题
回溯
如何将我们的扎气球问题转化成回溯算法呢？这个应该不难想到的，我们其实就是想穷举戳气球的顺序，不同的戳气球顺序可能得到不同的分数，我们需要把所有可能的分数中最高的那个找出来，对吧。
- 那么，这不就是一个「全排列」问题嘛，我们前文 回溯算法框架套路详解 中有全排列算法的详解和代码，其实只要稍微改一下逻辑即可，伪码思路如下：
- 回溯算法就是这么简单粗暴，但是相应的，算法的效率非常低。这个解法等同于全排列，所以时间复杂度是阶乘级别，非常高，题目说了nums的大小n最多为 500，所以回溯算法肯定是不能通过所有测试用例的。
动规
这个动态规划问题和我们之前的动态规划系列文章相比有什么特别之处？为什么它比较难呢？
- 因为我们每戳破一个气球nums[i]，得到的分数和该气球相邻的气球nums[i-1]和nums[i+1]是有相关性的。
- 我运用动态规划算法的一个重要条件：子问题必须独立。所以对于这个戳气球问题，如果想用动态规划，必须巧妙地定义dp数组的含义，避免子问题产生相关性，才能推出合理的状态转移方程。
如何定义dp数组呢？
- 对问题简单转化。题目说可认为nums[-1] = nums[n] = 1，那我们先直接把两个边界加进去，形成一个新数组points。现在气球的索引变成了从1到n，points[0]和points[n+1]可认为是两个「虚拟气球」。
- 那么我们可以改变问题：在一排气球points中，请你戳破气球0和气球n+1之间的所有气球（不包括0和n+1），使得最终只剩下气球0和气球n+1两个气球，最多能够得到多少分？
- 现在定义dp数组dp[i][j] = x：戳破气球 i 和 j 之间（开区间，不包括i和j）的所有气球，获得的最高分数x。
- 那么根据这个定义，题目要求的结果就是dp[0][n+1]的值，而 base case 就是dp[i][j] = 0，其中0 <= i <= n+1, j <= i+1，因为这种情况下，开区间(i, j)中间根本没有气球可以戳。
根据这个dp数组来推导状态转移方程，实际上就是在思考怎么「做选择」，也就是题目最有技巧的部分：
- 不就是想求戳破气球i和气球j之间的最高分数吗，如果「正向思考」，就只能写出前文的回溯算法；我们需要「反向思考」，想一想气球i和气球j之间最后一个被戳破的气球可能是哪一个？
「状态」和「选择」：i和j就是两个「状态」，最后戳破的那个气球k就是「选择」。
- 你不是要最后戳破气球k吗？那得先把开区间(i, k)的气球都戳破，再把开区间(k, j)的气球都戳破；最后剩下的气球k，相邻的就是气球i和气球j，这时候戳破k的话得到的分数就是points[i]points[k]points[j]。
- 那么戳破开区间(i, k)和开区间(k, j)的气球最多能得到的分数是多少呢？嘿嘿，就是dp[i][k]和dp[k][j]，这恰好就是我们对dp数组的定义嘛！
- 由于是开区间，dp[i][k]和dp[k][j]不会影响气球k；而戳破气球k时，旁边相邻的就是气球i和气球j了，最后还会剩下气球i和气球j，这也恰好满足了dp数组开区间的定义。
- 根据刚才对dp数组的定义，如果最后一个戳破气球k，dp[i][j]的值应该为：
那么对一组给定的i和j，只要穷举i < k < j的所有气球k，选得分最高的作为dp[i][j]的值 —— 状态转移方程：
但是还有问题：对于k的穷举仅仅是在做「选择」，但是应该如何穷举「状态」i和j呢？
关于「状态」的穷举，最重要的一点就是：状态转移所依赖的状态必须被提前计算出来。
dp[i][j]依赖的状态是dp[i][k]和dp[k][j]，那么必须保证：计算dp[i][j]时，dp[i][k]、dp[k][j]已被计算出（i < k < j）
- 那么应该如何安排i和j的遍历顺序，来提供上述的保证呢？我们前文 动态规划答疑篇 写过处理这种问题的一个鸡贼技巧：根据 base case 和最终状态进行推导。
base case + 最终状态
任意dp[i][j]以及对应的dp[i][k] dp[k][j]
为了达到这个要求，有两种遍历方法：斜着遍历 和 从下到上遍历
.
自下而上的遍历 代码
若有收获，就点个赞吧
0 人点赞
