Leetcode 题解算法之动态规划
505 / 1 / 创建于 4年前 /
Remember 的个人博客
开篇
我记得我之前有写过一点动态规划的文章，这两天刚好重新回顾了下 DP ，查阅的一些资料，再结合 Leetcode 的练习题，根据自己的理解，来重新认识一些动态规划。这篇文章的总体流程就是介绍动态规划的一些场景，解题思路，以及题目解析，我并不喜欢用一些专业的术语去介绍动态规划，这不是我的风格，而且我解释的也没有 Google 的好。
✏️动态规划的场景
我觉得动态规划是挺难理解的，可能就在于它的思想不符合正常人的思维方式。它的解题就像递归那样，已经不能按照人脑去一步步去追踪结果，然后返回了值，想想自己在学习递归的时候，有没有脑子里一直在想这个递归过程的调用，我这么干过! 这一步应该交给计算机，而动态规划需要我们定义状态，然后推出状态转移方程，状态转移方程找到之后，其实题目也就解决一半了。
动态规划的一些场景，典型的比如求一些最大最小值，背包问题，爬楼梯......，下面从一个例子中慢慢去了解动态规划吧，从典型的爬楼梯开始吧。这篇文章涉及到的所有题目都是以动态规划的思想解题，并不是说这道题只能用动态规划来解，不存在的。
其实我们求 n 阶台阶的总走法和 n-1 阶台阶的总走法本质上一样的，也就是说这个问题可以被分解为包含最优子结构的子问题。求这个解是可以从它的子问题的解推导出来的。
1.当 n =1 时，肯定只有一种走法，也就是向上走一步(dp[1]=1)。当 n=2 时，两种走法(dp[2]=2)，一种每一次走一步，两次到达，一种一次走两步一次到顶。
对于 n 层台阶，当前可以从两个位置上来:
2.从第 n-1 的位置向上迈进一步
3.从第 n-2 的位置向上迈进二步
从上面的第一点我们可以知道初始的状态，从第二第三点我们可以得出第 n 层台阶的总走法 = 它的下一层台阶的总走法+它的下下一层的台阶的总走法，为什么，因为到达当前层只有两种情况，要么从下一层跳一步，要么从下下一层跳两步。好了，这道题到这就已经解完了。你可能会问，那你刚说的动态规划呢?我说完了啊。上面的分析过程就是动态规划啊。就像我刚才说的，动态规划背后的思想简单概括就是，若要解一个指定的问题，我们需要解它的不同部分问题(子问题)，再合并子问题求出最终想要的解。
因此，动态规划解题最重要的两个步骤:
1.状态的定义 dp[1]=1，dp[2]=1
2.状态转移的方程 dp[n]=dp[n-1]+dp[n-2]
这里的 dp[n] 表示的含义是当台阶为 n 时，总共有多少走种走法。就像上面说的， n 层台阶的总走法 = 它的下一层台阶的总走法+它的下下一层的台阶的总走法，我们并不需要关心 dp[n-1] 和 dp[n-2] 这个过程是如何推导出来的，我们只关心它的状态值。只要定义好了状态，找出状态转移方程，这个题目其实就已经解了一大半了。接下来实现一下具体的代码:
/**
* @param Integer $n
* @return Integer
*/
function climbStairs($n) {
if($n==1) return 1;
$dp[1]=1;
$dp[2]=2;
for($i=3;$i<=$n;$i++){
$dp[$i]=$dp[$i-1]+$dp[$i-2];
}
return $dp[$n];
}嗯，到这里。其实这道题也就解出来了，但是，千万别觉得动态规划就这点东西。这道题目只是入门级的题目，并不是什么复杂的场景，状态的定义以及状态转移方程相对来说易于推导出来。实际情况下，对于这两步的推导是有点难度的，有时候可能定义一维的状态还不够，需要二维(接下来的题目会涉及到多维的)......说到这，其实动态规划的本质就是一个空间换时间的思想。但是请记住，动态规划解题思路最重要的两步就是状态的定义以及状态转移方程。动态规划区别于贪心算法的地方在于，它就像是获取了上帝的视角，每次能获取到全局的最优解，而不像贪心，每次得到是只是局部最优。单这一题过于无趣，接下来我会带上 Leecode 不同题型来认识动态规划，从简单到复杂题型。
Leetcode 120. 三角形最小路径和
这道题本身就是一个二维数组，所以我们再定义状态时候也定义一个二维数组(先不考虑压缩空间)。$dp[$i][$j] 表示从底部到 (i,j) 位置最短路径和，初始的 dp 值就等于最后一排的值，同样的道理，这里定义的 dp[i][j] 的意思是从底部到达二维数组 (i,j) 的最小和。那么状态转移方程呢？从题目中可以看到这么一句话 每一步只能移动到下一行中相邻的结点上，对于我们这里，是从下往上计算，那么对应的状态转移方程:
当前(i,j) 位置和的最小值： $dp[$i][$j]=$triangle[$i][$j]+min($dp[$i+1][$j],$dp[$i+1][$j+1])
比如图中例子5那么它的dp转移方程即:$dp[2][1]=它可以由下层的$dp[3][1]+它自身 或者 下层的$dp[3][2]+它自身值 哪个路径短，就是哪个。
请注意上面出现两个变量 $triangle[$i][$j] 以及 $dp[$i][$j] ,前者表示的是表中二维数组第 i 行 j 列上的值,而后者是我们定义的状态值表示在(i,j)这个位置上总和的最小值，它是由之前的一步步推导出来的。而这个推导的过程我们是不关心的，我们只关心它的结果。
为什么反着推呢，原因很简单，因为最后的值必然出现在$dp[0][0]的位置，顶层只有一个元素。
/**
* @param Integer[][] $triangle
* @return Integer
*/
function minimumTotal($triangle)
{
if (empty(count($triangle))) {
return 0;
}
for ($i = count($triangle) - 1; $i >= 0; $i--) {
for ($j = 0; $j < count($triangle[$i]); ++$j) {
$triangle[$i][$j] += min($triangle[$i + 1][$j], $triangle[$i + 1][$j + 1]);
}
}
return $triangle[0][0];
}这里代码做了一点细微的处理，不需要额外定义 dp[]，因为我们在进入当前层计算最小和值的时候，只需要下一层最小和的状态值，而不是数组具体位置的值本身，所以每次算完可以覆盖原先的值，给上一层使用。
Leetcode 152. 乘积最大子序列
我们还是先按照之前说的先定义状态，然后求出状态转移方式。这道题用一个一维数组存储dp 即可。
DP[i] 代表从下标0到下标i这个范围内的连续子数组最大的乘积
状态转移方程:
DP[i+1] = DP[i] * 当前下标的值
这里有个关键点在于 DP 保存的是当前位置连续子数组的最大的乘积，但是我们并不知道当前下标的值是负数还是正数，如果是负数，那么 DP[i+1] 将会是一个最小值,所以只是单纯的这样定义状态是不行的。如果是负数的话，我们就应该选取前面推出的负数最大值 即最小值。如果是正数的话我们才应该把之前的最大 DP 拿过来直接相乘，所以这里需要定义两个状态。最大值的状态 $max[$i] 和最小值的状态 $min[$i]。
/**
* @param Integer[] $nums
* @return Integer
*/
function maxProduct($nums)
{
$max[0] = $min[0] = $res = $nums[0];
for ($i = 1; $i < count($nums); $i++) {
$max[$i] = max($max[$i - 1] * $nums[$i], $min[$i - 1] * $nums[$i], $nums[$i]);
$min[$i] = min($max[$i - 1] * $nums[$i], $min[$i - 1] * $nums[$i], $nums[$i]);
$res = max($res, $max[$i]);
}
return $res;
}
如果觉得这样看着变扭，多定义两个变量作为中转。
/**
* @param Integer[] $nums
* @return Integer
*/
function maxProduct($nums)
{
$max = $min = $res = $nums[0];
for ($i = 1; $i < count($nums); $i++) {
$mx = $max;
$mn = $min;
$max = max(max($nums[$i], $nums[$i] * $mx), $nums[$i] * $mn);
$min = min(min($nums[$i], $nums[$i] * $mx), $nums[$i] * $mn);
$res = max($res, $max);
}
return $res;
}Leetcode 300. 最长上升子序列
这道题并不是要求连续的，只要后面的数比前面的大，那么就是可以被添加到连续上升子序列中的，只是说每次应该加入较小的数字，才能给后面腾出更多的位置，道理是这么说的。
默认开始的状态一定是1 因为就算是全部递减的值，它的最长上升子序列至少还是等于1，也就是它本身。
DP[i]=Max(DP[i],DP[j-1]+1) 如果$nums[i-1]<$nums[$j],说明此时$nums[i]也能加入到子序列中
这个状态转移方程是什么意思呢？可以先看代码在进行解释。
/**
* @param Integer[] $nums
* @return Integer
*/
function lengthOfLIS($nums)
{
$size = count($nums);
if ($size < 2) return $size;
$dp[0] = $res = 1;
for ($i = 1; $i < count($nums); $i++) {
$dp[$i] = 1;
for ($j = 0; $j < $i; $j++) {
if ($nums[$j] < $nums[$i]) {
$dp[$i] = max($dp[$i], $dp[$j] + 1);
}
}
$res = max($res, $dp[$i]);
}
return $res;
}两层遍历，第一层表示的到第 i 个元素，整体的意思是，每次到第 i 个元素的时候，就去看 i 之前的已经推导出来的状态。j 的值就是0到 i,只要 $nums[$j] < $nums[$i] 说明 i 的位置可以利用之前推导的结果组成一个最长上升的子序列。所以就把之前推导出的 $dp[$j] +1，和已经推导出的 $dp[$i] 进行比较，获取最大值，重新存储在 $dp[i] 中。然后每次全局更新最大上升子序列值，最后返回即可。
Leetcode 121. 买卖股票的最佳时机
这系列的题目很有意思,这道题只能有一次交易，就是求利益最大化的买卖。对于这里的状态定义，可能一开始难以想到，我们可以这样想，每一天我们的状态只会有三种，未持有股票(没购买过)，持有股票以及未持有股票(抛售了):
初始状态
$dp[0][0]=$dp[0][2]=0，$dp[0][1]= -第一天的价格。什么意思呢，其实就是初始状态的定义表示第一天没买股票，那么收益的值0，即$dp[0][0]=0，$dp[0][2]表示第一天卖出股票的收益，因为第一天不存在卖，所以初始值也是0。最后看$dp[0][1]= -第一天的价格，这里表示如果第一天买了股票那么收益当然是负数的，即购买的价格。状态定义完了，接下来就是状态转移方程了。也就是
$dp[i][0]，$dp[i][1]以及$dp[i][2]咋么转移，我们可以这么想第i天持有未购买的情况只能是前面的也没购买，第i天持有的情况分为两种情况，一种是前一天已经持有了或者是前一天也是未持有状态然后今天购买持有了。剩下的第i天已出售情况只能是前一天持有的状态然后今天抛售了。这个理清楚了，代码也就好写了。
/**
* @param Integer[] $prices
* @return Integer
*/
function maxProfit($prices)
{
$dp[0][0] = $dp[0][2] = 0;
$dp[0][1] = -$prices[0];
$res = 0;
for ($i = 1; $i < count($prices); $i++) {
$dp[$i][0] = $dp[$i - 1][0];
$dp[$i][1] = max($dp[$i - 1][1], $dp[$i - 1][0] - $prices[$i]);
$dp[$i][2] = $dp[$i - 1][1] + $prices[$i];
$res = max($res, $dp[$i][0], $dp[$i][1], $dp[$i][2]);
}
return $res;
}Leetcode 122. 买卖股票的最佳时机 II
这是上一题的扩展，上一题只能交易一次，这一题可以多次交易。这道题我不用三个维护状态维护了，只有两种状态，第 i 天 未持有股票 和第 i 天持有股票。转移方程嘛就很好理解了，持有股票最大值，之前持有的最大值和之前不持有股票今天买了，取最大值。至于不持有股票最大值也分为两种，之前就一直不持有股票值和之前持有股票值今天卖了，取最大值，最后取 dp 数组中不持有股票最后的值。因为每一次更新的都是到 i 天的交易最大值，所以最后得到的必然是全局最大值。
/**
* @param Integer[] $prices
* @return Integer
*/
function maxProfit($prices)
{
if (count($prices) == 0) return 0;
$dp[0][1] = -$prices[0];
$dp[0][0] = 0;
for ($i = 1; $i < count($prices); $i++) {
$dp[$i][1] = max($dp[$i - 1][1], $dp[$i - 1][0] - $prices[$i]);
$dp[$i][0] = max($dp[$i - 1][1] + $prices[$i], $dp[$i - 1][0]);
}
return $dp[count($prices) - 1][0];
}Leetcode 123. 买卖股票的最佳时机 III 终极难题
这道题又是上一版的扩展，因为规定了具体的交易次数，所以这一题单单是二维数据也必然不够了，因为我们还需要一个维度用来维护第 k 次交易的状态。这道题难度确实挺大的。
DP[i][k][j] 定义了一个三维数组，i 表示第几天 k 表示第几次交易 j 表示是否持有股票
然后分情况，第 i 天第 k 次都用两种情况持有股票和没有持有股票这两种状态。自己看代码理解一下吧。
/**
* @param Integer[] $prices
* @return Integer
*/
function maxProfit($prices)
{
$res = 0;
$dp[0][0][0] = 0;
$dp[0][0][1] = -$prices[0];
$dp[0][1][0] = -$prices[0];
$dp[0][1][1] = -$prices[0];
$dp[0][2][0] = 0;
for ($i = 1; $i < count($prices); $i++) {
$dp[$i][0][0] = $dp[$i - 1][0][0];
$dp[$i][0][1] = max($dp[$i - 1][0][1], $dp[$i - 1][0][0] - $prices[$i]);
$dp[$i][1][0] = max($dp[$i - 1][1][0], $dp[$i - 1][0][1] + $prices[$i]);
$dp[$i][1][1] = max($dp[$i - 1][1][0] - $prices[$i], $dp[$i - 1][1][1]);
$dp[$i][2][0] = max($dp[$i - 1][2][0], $dp[$i - 1][1][1] + $prices[$i]);
}
$length = count($prices) - 1;
return max($res, $dp[$length][0][0], $dp[$length][1][0], $dp[$length][2][0]);
}
另外，结合自己做题之路，分享一个好方法，千万千万别一题题做下来，既然刷题当然需要针对性，一定要专门针对性的练习，哪一块数据结构或者算法短板，没关系，先补下知识，然后想刷二分？可以，Leecode(如果你看的是英文版的话，Leetcode-cn 的话更省事了，直接看中文) 首页点击 tags,选择 Binary Serach,这样针对性的学习，我想成长只是时间的问题吧。因为你帅我才告诉你。
动态规划的题型很多，这里到此为止了。剩下的可以自己去 Leetcode 专门查找对应的题型刷题。
公众号记录刷题 Leetcode 以及学习之路，:目前粉丝量惊人，达到了 100000/1000 人。😁欢迎加入。
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：