動態規劃-第2篇

前言：在上一篇文章中，我們了解了動態規劃的基本概念和解決問題的基本思路。通過分解問題、存儲子問題的解，動態規劃為我們提供了高效的解決方案。然而，動態規劃并不是一成不變的，它有很多不同的技巧和變種，能夠應對各類復雜問題。

在本篇文章中，我們將深入探討一些常見的動態規劃問題及其解法，學習如何巧妙地設計狀態轉移方程，優化空間復雜度，并進一步掌握動態規劃的核心思想。通過具體實例，你將能夠更好地理解如何在實際開發中運用動態規劃來解決復雜問題。🌼🌼

?7. 禮物的最?價值（medium）

?1. 題?鏈接：LCR 166. 珠寶的最高價值

2.解法（動態規劃）：

算法思路：

?1. 狀態表?：

對于這種「路徑類」的問題，我們的狀態表??般有兩種形式：

i. 從 [i, j] 位置出發，巴拉巴拉；

ii. 從起始位置出發，到達 [i, j] 位置，巴拉巴拉。

這?選擇第?種定義狀態表?的?式：

dp[i][j] 表?：?到 [i, j] 位置處，此時的最?價值。

2. 狀態轉移?程：

對于 dp[i][j] ，我們發現想要到達 [i, j] 位置，有兩種?式：

i. 從 [i, j] 位置的上? [i - 1, j] 位置，向下??步，此時到達 [i, j] 位置能

拿到的禮物價值為 dp[i - 1][j] + grid[i][j] ；

ii. 從 [i, j] 位置的左邊 [i, j - 1] 位置，向右??步，此時到達 [i, j] 位置能拿到的禮物價值為 dp[i][j -1] + grid[i][j]

我們要的是最?值，因此狀態轉移?程為：

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j] 。

3. 初始化：

可以在最前?加上?個「輔助結點」，幫助我們初始化。使?這種技巧要注意兩個點：

i. 輔助結點??的值要「保證后續填表是正確的」；

ii. 「下標的映射關系」。

在本題中，「添加??」，并且「添加?列」后，所有的值都為 0 即可。

4. 填表順序：

根據「狀態轉移?程」，填表的順序是「從上往下填寫每??」，「每??從左往右」。

5. 返回值：

根據「狀態表?」，我們應該返回 dp[m][n] 的值。

3.C++ 算法代碼：

class Solution {
public:int jewelleryValue(vector<vector<int>>& vv) {int m=vv.size();int n=vv[0].size();vector<vector<int>>dp(m+1,vector<int>(n+1));dp[0][0]=0;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j]=max(dp[i-1][j],dp[i][j-1])+vv[i-1][j-1];}}return dp[m][n];}
};

8.下降路徑最?和（medium）

?1. 題?鏈接：931. 下降路徑最小和 - 力扣（LeetCode）

2. 解法（動態規劃）：

算法思路：

關于這?類題，由于我們做過類似的，因此「狀態表?」以及「狀態轉移」是?較容易分析出來的。

?較難的地?可能就是對于「邊界條件」的處理。

1. 狀態表?：

對于這種「路徑類」的問題，我們的狀態表??般有兩種形式：

i. 從 [i, j] 位置出發，到達?標位置有多少種?式；

ii. 從起始位置出發，到達 [i, j] 位置，?共有多少種?式

這?選擇第?種定義狀態表?的?式：

dp[i][j] 表?：到達 [i, j] 位置時，所有下降路徑中的最?和。

2. 狀態轉移?程：

對于普遍位置 [i, j] ，根據題意得，到達 [i, j] 位置可能有三種情況： i. 從正上? [i - 1, j] 位置轉移到 [i, j] 位置；

ii. 從左上? [i - 1, j - 1] 位置轉移到 [i, j] 位置；

iii. 從右上? [i - 1, j + 1] 位置轉移到 [i, j] 位置；

我們要的是三種情況下的「最?值」，然后再加上矩陣在 [i, j] 位置的值。

于是 dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i - 1][j + 1])) + matrix[i][j] 。

3. 初始化：

可以在最前?加上?個「輔助結點」，幫助我們初始化。使?這種技巧要注意兩個點：

i. 輔助結點??的值要「保證后續填表是正確的」；

ii. 「下標的映射關系」。

在本題中，需要「加上??」，并且「加上兩列」。所有的位置都初始化為?窮?，然后將第??

初始化為 0 即可。

4. 填表順序：

根據「狀態表?」，填表的順序是「從上往下」。

5. 返回值：

注意這?不是返回 dp[m][n] 的值！

題?要求「只要到達最后??」就?了，因此這?應該返回「 dp 表中最后??的最?值」。

3.C++ 算法代碼

class Solution
{
public:
int minFallingPathSum(vector<vector<int>>& matrix)
{
// 1. 創建 dp 表
// 2. 初始化
// 3. 填表
// 4. 返回結果
int n = matrix.size();
vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));
// 初始化第??
for(int j = 0; j < n + 2; j++) dp[0][j] = 0;for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j
+ 1])) + matrix[i - 1][j - 1];
int ret = INT_MAX;
for(int j = 1; j <= n; j++)
ret = min(ret, dp[n][j]);
return ret;
}
}

9. 最?路徑和（medium）

1.題目鏈接：64. 最小路徑和 - 力扣（LeetCode）?

2.??解法（動態規劃）：

算法思路：

像這種表格形式的動態規劃，是?常容易得到「狀態表?」以及「狀態轉移?程」的，可以歸結到

「不同路徑」?類的題??。

1. 狀態表?：

對于這種路徑類的問題，我們的狀態表??般有兩種形式：

i. 從 [i, j] 位置出發，巴拉巴拉；

ii. 從起始位置出發，到達 [i, j] 位置，巴拉巴拉。

這?選擇第?種定義狀態表?的?式：

dp[i][j] 表?：到達 [i, j] 位置處，最?路徑和是多少。

2. 狀態轉移：

簡單分析?下。如果 dp[i][j] 表?到達到達 [i, j] 位置處的最?路徑和，那么到達 [i, j] 位置之前的??步，有兩種情況：

i. 從 [i - 1, j] 向下??步，轉移到 [i, j] 位置；

ii. 從 [i, j - 1] 向右??步，轉移到 [i, j] 位置。

由于到 [i, j] 位置兩種情況，并且我們要找的是最?路徑，因此只需要這兩種情況下的最?值，再加上 [i, j] 位置上本?的值即可。

也就是： dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

3. 初始化：

可以在最前?加上?個「輔助結點」，幫助我們初始化。使?這種技巧要注意兩個點：

i. 輔助結點??的值要「保證后續填表是正確的」；

ii. 「下標的映射關系」。

在本題中，「添加??」，并且「添加?列」后，所有位置的值可以初始化為?窮?，然后讓 dp[0][1] = dp[1][0] = 1 即可。

4. 填表順序：

根據「狀態轉移?程」的推導來看，填表的順序就是「從上往下」填每??，每??「從左往

后」。

5. 返回值：

根據「狀態表?」，我們要返回的結果是 dp[m][n] 。

3.C++ 算法代碼：

class Solution
{
public:
int minPathSum(vector<vector<int>>& grid)
{
// 1. 創建 dp 表
// 2. 初始化
// 3. 填表
// 4. 返回結果
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
dp[0][1] = dp[1][0] = 0;
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j -
1];
return dp[m][n];
}
}

10. 地下城游戲（hard）

?1. 題?鏈接：174. 地下城游戲 - 力扣（LeetCode）

2. 解法（動態規劃）：

算法思路：

1. 狀態表?：

這道題如果我們定義成：從起點開始，到達 [i, j] 位置的時候，所需的最低初始健康點數。那么我們分析狀態轉移的時候會有?個問題：那就是我們當前的健康點數還會受到后?的路徑的影響。也就是從上往下的狀態轉移不能很好地解決問題。

這個時候我們要換?種狀態表?：從 [i, j] 位置出發，到達終點時所需要的最低初始健康點

數。這樣我們在分析狀態轉移的時候，后續的最佳狀態就已經知曉。

綜上所述，定義狀態表?為：

dp[i][j] 表?：從 [i, j] 位置出發，到達終點時所需的最低初始健康點數。

2. 狀態轉移?程：

對于 dp[i][j] ，從 [i, j] 位置出發，下?步會有兩種選擇（為了?便理解，設 dp[i] [j] 的最終答案是 x）：

i. ?到右邊，然后?向終點

那么我們在 [i, j] 位置的最低健康點數加上這?個位置的消耗，應該要?于等于右邊位置的最低健康點數，也就是： x + dungeon[i][j] >= dp[i][j + 1] 。

通過移項可得： x >= dp[i][j + 1] - dungeon[i][j] 。因為我們要的是最?值，因此這種情況下的 x = dp[i][j + 1] - dungeon[i][j] ；

ii. ?到下邊，然后?向終點

那么我們在 [i, j] 位置的最低健康點數加上這?個位置的消耗，應該要?于等于下邊位置的最低健康點數，也就是： x + dungeon[i][j] >= dp[i + 1][j] 。

通過移項可得： x >= dp[i + 1][j] - dungeon[i][j] 。因為我們要的是最?值，因此這種情況下的 x = dp[i + 1][j] - dungeon[i][j] ；

綜上所述，我們需要的是兩種情況下的最?值，因此可得狀態轉移?程為：

dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]

但是，如果當前位置的 dungeon[i][j] 是?個?較?的正數的話， dp[i][j] 的值可能變

成 0 或者負數。也就是最低點數會?于 1 ，那么騎?就會死亡。因此我們求出來的

如果?于等于 0 的話，說明此時的最低初始值應該為 1 。處理這種情況僅需讓 ?dp[i] [j] ?與 ?1 ?取?個最?值即可：?

dp[i][j] = max(1, dp[i][j])

3. 初始化：

可以在最前?加上?個「輔助結點」，幫助我們初始化。使?這種技巧要注意兩個點：

i. 輔助結點??的值要「保證后續填表是正確的」；

ii. 「下標的映射關系」。

在本題中，在 dp 表最后?添加??，并且添加?列后，所有的值都先初始化為?窮?，然后讓 dp[m][n - 1] = dp[m - 1][n] = 1 即可。

4. 填表順序：

根據「狀態轉移?程」，我們需要「從下往上填每??」，「每??從右往左」。

5. 返回值：

根據「狀態表?」，我們需要返回 dp[0][0] 的值。

3.C++ 算法代碼：

class Solution
{
public:
int calculateMinimumHP(vector<vector<int>>& dungeon)
{
int m = dungeon.size(), n = dungeon[0].size();
// 建表 + 初始化
vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
dp[m][n - 1] = dp[m - 1][n] = 1;
// 填表
for(int i = m - 1; i >= 0; i--)
for(int j = n - 1; j >= 0; j--)
{
dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
dp[i][j] = max(1, dp[i][j]);
}
// 返回結果
return dp[0][0];
}
}

簡單多狀態 dp 問題

11. 按摩師（easy）

打家劫舍問題的變形~ ?偷變成了按摩師

1. 題?鏈接：面試題 17.16. 按摩師

?2. 解法（動態規劃）：

算法思路：

1. 狀態表?：

對于簡單的線性 dp ，我們可以?「經驗 + 題?要求」來定義狀態表?：

i. 以某個位置為結尾，巴拉巴拉；

ii. 以某個位置為起點，巴拉巴拉。

這?我們選擇?較常?的?式，以某個位置為結尾，結合題?要求，定義?個狀態表?：

dp[i] 表?：選擇到 i 位置時，此時的最?預約時?。

但是我們這個題在 i 位置的時候，會?臨「選擇」或者「不選擇」兩種抉擇，所依賴的狀態需要

細分：

? f[i] 表?：選擇到 i 位置時， nums[i] 必選，此時的最?預約時?；

? g[i] 表?：選擇到 i 位置時， nums[i] 不選，此時的最?預約時?。

2. 狀態轉移?程：

因為狀態表?定義了兩個，因此我們的狀態轉移?程也要分析兩個：

對于 f[i] ：

? 如果 nums[i] 必選，那么我們僅需知道 i - 1 位置在不選的情況下的最?預約時?，

然后加上 nums[i] 即可，因此 f[i] = g[i - 1] + nums[i] 。

對于 g[i] ：

? 如果 nums[i] 不選，那么 i - 1 位置上選或者不選都可以。因此，我們需要知道 i置上選或者不選兩種情況下的最?時?，因此 g[i] = max(f[i - 1], g[i])

3. 初始化：

這道題的初始化?較簡單，因此?需加輔助節點，僅需初始化 f[0] = nums[0], g[0] = 0即可。

4. 填表順序

根據「狀態轉移?程」得「從左往右，兩個表?起填」。

5. 返回值

根據「狀態表?」，應該返回 max(f[n - 1], g[n - 1]) 。

3.C++ 算法代碼：

class Solution {
public:
int massage(vector<int>& nums) {
// 1. 創建?個 dp 表
// 2. 初始化
// 3. 填表
// 4. 返回值
int n = nums.size();
if(n == 0) return 0; // 處理邊界條件
vector<int> f(n);
auto g = f;
f[0] = nums[0];
for(int i = 1; i < n; i++)
{
f[i] = g[i - 1] + nums[i];
g[i] = max(f[i - 1], g[i - 1]);
}
return max(f[n - 1], g[n - 1]);
}
};

12. 打家劫舍II （medium）

1.題目鏈接：?213. 打家劫舍 II - 力扣（LeetCode）

2. 解法（動態規劃）

算法思路：

這?個問題是「打家劫舍I」問題的變形。

上?個問題是?個「單排」的模式，這?個問題是?個「環形」的模式，也就是?尾是相連的。但

是我們可以將「環形」問題轉化為「兩個單排」問題：

a. 偷第?個房屋時的最??額 x ，此時不能偷最后?個房?，因此就是偷 [0, n - 2] 區間的房?；

b. 不偷第?個房屋時的最??額 y ，此時可以偷最后?個房?，因此就是偷 [1, n - 1] 區間的房?；

兩種情況下的「最?值」，就是最終的結果。

因此，問題就轉化成求「兩次單排結果的最?值」

3. C++算法代碼：

class Solution {
public:int rob(vector<int>& nums) {int n=nums.size();int f1=test(nums,2,n-2)+nums[0];//第一個偷的話int g1=test(nums,1,n-1);//第一個不偷的話return max(f1,g1);}int test(vector<int>& nums,int left,int right)//與按摩問題一樣{if(left>right)return 0;int n=nums.size();vector<int> f(n);f[left]=nums[left];auto g=f;g[left]=0;for(int i=left+1;i<=right;i++){f[i]=g[i-1]+nums[i];g[i]=max(f[i-1],g[i-1]);}return max(f[right],g[right]);}
};