數據結構與算法學習筆記----動態規劃·數字三角形

@@ author: 明月清了個風
@@ first publish time: 2025.4.23

ps??終于開始提高課的題啦，借的人家的號看，以后給y總補票叭，提高課的題比之前的多很多啊哈哈哈哈，基本上每種題型都對應了難度逐步上升的幾道題，和基礎課的題相比加了一層應用，需要從題目中抽象出模型才能解題。

數字三角形的題為動態規劃的經典模型，基礎課中已經講過了，在這里。提高課的是在此基礎上的進一步延伸和應用，但原理其實沒有變。

Acwing 1015. 摘花生

Hello Kitty想摘點花生送給她喜歡的米老鼠。

她來到一片有網格狀道路的矩形花生地(如下圖)，從西北角進去，東南角出來。

地里每個道路的交叉點上都有種著一株花生苗，上面有若干顆花生，經過一株花生苗就能摘走該它上面所有的花生。

Hello Kitty只能向東或向南走，不能向西或向北走。

問Hello Kitty最多能夠摘到多少顆花生。

輸入格式

第一行是一個整數$T$，代表一共有多少組數據。

接下來是$T$組數據。

每組數據的第一行是兩個整數，分別代表花生苗的行數$R$和列數$C$。

每組數據的接下來$R$行數據，從北向南依次描述每行花生苗的情況。每行數據有$C$個整數，按從西向東的順序描述了該行每株花生苗上的花生數目$M$。

輸出格式

對每組輸入數據，輸出一行，內容為Hello Kitty能摘到得最多的花生顆數。

數據范圍

$1\le T\le 100$，

$1\le R,C\le 100$，

$0\le M\le 1000$

思路

對于動態規劃而言，和基礎課一樣，考慮狀態表示和狀態轉移。

對于狀態表示，使用f[i][j]，表示的集合是所有從(1, 1)走到(i, j)的路線，而要求的屬性是這個集合中的最大值。

對于狀態轉移或者說狀態計算，就是將上述集合進行劃分，找出其子集遞歸求解。而狀態劃分的很重要的一種方法就是根據最后一步操作進行劃分，也就是f[i][j]是怎么來的這一步。在這一題中，f[i][j]可以是從上面下來，也可以是從左邊過來，因此可以劃分為兩個子集f[i][j - 1]和f[i - 1][j]。需要注意的是，對于集合的劃分，最重要的兩個原則是不重不漏，其中不漏是任何情況都需要滿足的，因為每種方案都需要考慮，而不重在求最大值或最小值時可以不滿足，因為重復的計算并不會提高集合中的最值。

在上面已經將集合f[i][j]劃分為兩個集合f[i - 1][j]和f[i][j - 1]，那么求f[i][j]的最大值就是求這兩個子集的最大值再加上最后一步的權值即可。

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 110;int T;
int n, m;
int a[N][N];
int f[N][N];int main()
{cin >> T;while(T --){cin >> n >> m;for(int i = 1; i <= n; i ++)for(int j = 1; j <= m; j ++)cin >> a[i][j];for(int i = 1; i <= n; i ++)for(int j = 1; j <= m; j ++)f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j];cout << f[n][m] << endl;}return 0;
}

Acwing 1018. 最低通行費

一個商人穿過一個$N\times N$的正方形的網格，去參加一個非常重要的商務活動。他要從網格的左上角進，右下角出。每穿越中間1個小方格，都要花費1個單位時間。商人必須在$2N?1$個單位時間穿越出去。而在經過中間的每個小方格時，都需要繳納一定的費用。
這個商人期望在規定時間內用最少費用穿越出去。請問至少需要多少費用？
注意：不能對角穿越各個小方格（即，只能向上下左右四個方向移動且不能離開網格）。

輸入格式

第一行是一個整數$T$，表示正方形的寬度$N$。

后面$N$行，每行$N$個不大于$100$的整數，為網格上每個小方格的費用。

輸出格式

輸出一個整數，表示至少需要的費用。

數據范圍

$1\le N\le 100$

思路

其實還是和數字三角形一樣的模型，只是多了個迷惑的地方，給了步驟限制為$2N?1$，但是可以發現只要不回頭走就行。因此思路和代碼都是和上面一樣的。

需要注意的地方時，這一題求的集合的屬性是最小值，因此需要對邊界的地方進行特判和初始化。

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 110, inf = 1e9;int n;
int f[N][N];
int a[N][N];int main()
{cin >> n;for(int i = 1; i <= n; i ++)for(int j = 1; j <= n; j ++)cin >> a[i][j];for(int i = 1; i <= n; i ++)for(int j = 1; j <= n; j ++){if(i == 1 && j == 1) f[i][j] = a[i][j];else{f[i][j] = inf;if(i > 1) f[i][j] = min(f[i][j], f[i - 1][j] + a[i][j]);if(j > 1) f[i][j] = min(f[i][j], f[i][j - 1] + a[i][j]);}}cout << f[n][n] << endl;return 0;
}

Acwing 1027. 方格取數

設有N*N的方格圖($N\le 10$),我們將其中的某些方格中填入正整數,而其他的方格中則放入數字0。
某人從圖的左上角的$A$點$(1,1)$出發，可以向下行走，也可以向右走，直到到達右下角的B點$(N,N)$。在走過的路上，他可以取走方格中的數（取走后的方格中將變為數字0）。
此人從$A$點到$B$點共走兩次，試找出2條這樣的路徑，使得取得的數之和為最大。

輸入格式

第一行是一個整數$N$，表示$N\times N$的方格圖。

接下來每行有三個整數，第一個為行號數，第二個為列號數，第三個為在該行、該列上所放的數。

一行以"0 ,0 ,0"表示結束。

輸出格式

給出一個整數，表示兩條路徑上取得的最大的和。

數據范圍

$ N \le 10$

思路

這一題的變化是要走兩次。對于上面兩題而言都只需要計算一個路徑，而走兩次最大的變化就是同一個數只能被拿走一次。

首先思考是兩條路線一起走還是兩條路線先后走，因為每個數只能拿一次，因此兩條路線是完全獨立的兩條線，先走后走并不影響總和。可以直接對上面的狀態表示進行推廣，使用f[i1][j1][i2][j2]表示第一條路線走到了a[i1][j1]，第二條路線走到了a[i2][j2]的集合。

然后就是如何不重復走到同一個格子，因為不能回頭走，所以如果兩條線走到了同一個格子，那么肯定有$i_1+j_1=i_2+j_2$。

因此就有了下面的優化，上面這個狀態表示是四維的，雖然數據范圍很小，但是仍有優化空間，考慮到要對每個格子的坐標的和作比較，因此使用f[k][i1][i2]進行表示，其中k表示橫縱坐標的和，那么就有j1 = k - i1和j2 = k - i2，當i1 == i2時，可能出現兩條路線重合。

對于狀態劃分來說，和之前的題目一樣，使用最后一步進行劃分，只是這里會有兩條路線。因此可以根據第一條路線向右或向下，第二條路線向右或向下分為四類：下下，下右，右下，右右。

以下下的組合為例說明狀態計算方法：

• 對于下下的組合來說，兩條路線都是向下走到了最新的一步，因此是分別從a[i1][j1 - 1]和a[i2][j2 - 1]走到了最新位置，這兩個地方的狀態可以由$f[k?1][i1][i2]$表示，然后判斷一下是否重合即可，重合的話那就只加上一個a[i1][j1]即可，不重合就要同時加上a[i1][j1]和a[i2][j2]。

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 20;int n;
int f[N * 2][N][N];
int w[N][N];int main()
{cin >> n;int a, b, c;while(cin >> a >> b >> c, a || b || c) w[a][b] = c;for(int k = 2; k <= n + n; k ++)for(int i1 = 1; i1 <= n; i1 ++)for(int i2 = 1; i2 <= n; i2 ++){int j1 = k - i1, j2 = k - i2;if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n){int t = w[i1][j1];if(i1 != i2) t += w[i2][j2];int &x = f[k][i1][i2];x = max(x, f[k - 1][i1- 1][i2 - 1] + t);x = max(x, f[k - 1][i1 - 1][i2] + t);x = max(x, f[k - 1][i1][i2 - 1] + t);x = max(x, f[k - 1][i1][i2] + t);}}cout << f[n + n][n][n] << endl;return 0;
}

Acwing 275. 傳紙條

小淵和小軒是好朋友也是同班同學，他們在一起總有談不完的話題。

一次素質拓展活動中，班上同學安排坐成一個$m$行$n$列的矩陣，而小淵和小軒被安排在矩陣對角線的兩端，因此，他們就無法直接交談了。

幸運的是，他們可以通過傳紙條來進行交流。

紙條要經由許多同學傳到對方手里，小淵坐在矩陣的左上角，坐標$(1,1)$,小軒坐在矩陣的右下角，坐標$(m,n)$。

從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。

在活動進行中，小淵希望給小軒傳遞一張紙條，同時希望小軒給他回復。

班里每個同學都可以幫他們傳遞，但只會幫他們一次，也就是說如果此人在小淵遞給小軒紙條的時候幫忙，那么在小軒遞給小淵的時候就不會再幫忙，反之亦然。

還有一件事情需要注意，全班每個同學愿意幫忙的好感度有高有低（注意：小淵和小軒的好心程度沒有定義，輸入時用$0$表示），可以用一個$0～100$的自然數來表示，數越大表示越好心。

小淵和小軒希望盡可能找好心程度高的同學來幫忙傳紙條，即找到來回兩條傳遞路徑，使得這兩條路徑上同學的好心程度之和最大。

現在，請你幫助小淵和小軒找到這樣的兩條路徑。

輸入格式

第一行有$2$個用空格隔開的整數$m$和$n$，表示學生矩陣有$m$行$n$列。

接下來$m$行是一個$m\times n$的矩陣，矩陣中第$i$行$j$列的整數表示坐在第$i$行$j$列的學生的好心程度，每行的$n$個整數之間用空格隔開。

輸出格式

輸出一個整數，表示來回兩條路上參與傳遞紙條的學生的好心程度之和的最大值。

數據范圍

$1\le n,m\le 50$

思路

這一題與上一題的區別是同一個格子不能走第二次，在上一題中，如果走到了重合的格子會少加一次權重，而這里要求是不能走第二次，其實也很好解決，也就是要證明有兩條不相交的路線具有最大的好心程度之和。

首先要解決的是兩條路線相交的問題，如果存在兩條相交的路線，如下圖所示，從A到B的兩條路線中有兩個交點C與D。

因為經過的格子的權重是確定的，因此可以對兩條路線上的部分片段進行交換，變換后入下圖：

因此得證相交的路線可以通過路線的變形使其變成等效但僅有相交點而不相錯的情況。

根據題意，同一個點不能走第二次，因此考慮如何處理相交點$C$和$D$。通過觀察上圖可以發現，對于重合點C來講，該路線可以轉化為下圖所示經過點E的路線，且該路線的好心程度之和一定優于原路線（將重合點C權重清零后第二次不再計算）

根據上一題的代碼可以發現，其實當走到同一點時，我們只會添加一次權重，因此這里的值一定會比經過點E的路線值小，也就是題目所限制的非法路線算出來的值一定小于最優解合法路的值，因此上一題的代碼中不必為了這一題進行修改，代碼稍有變動。

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 60;int n, m;
int f[N * 2][N][N];
int w[N][N];int main()
{cin >> n >> m;for(int i = 1; i <= n; i ++)for(int j = 1; j <= m; j ++)cin >> w[i][j];for(int k = 2; k <= n + m; k ++)for(int i1 = 1; i1 <= n; i1 ++)for(int i2 = 1; i2 <= n; i2 ++){int j1 = k - i1, j2 = k - i2;if(j1 >= 1 && j1 <= m && j2 >= 1 && j2 <= m){int t = w[i1][j1];if(i1 != i2) t += w[i2][j2];int &x = f[k][i1][i2];x = max(x, f[k - 1][i1- 1][i2 - 1] + t);x = max(x, f[k - 1][i1 - 1][i2] + t);x = max(x, f[k - 1][i1][i2 - 1] + t);x = max(x, f[k - 1][i1][i2] + t);}}cout << f[n + m][n][n] << endl;return 0;
}