經典數字三角形問題
題目描述
給定一個如下圖所示的數字三角形，從頂部出發，在每一結點可以選擇移動至其左下方的結點或移動至其右下方的結點，一直走到底層，要求找出一條路徑，使路徑上的數字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 複制
思路分析
分析：本題是一道非常經典的dp問題，數字三角形問題可以從上往下走來尋找最大路徑，也可以從下往上走來尋找最大路徑，我們可以發現從上往下走我們要分析每個數是怎麼走到這裡的，比如0這個數字，隻能從左邊走過來，右邊走不過來，這樣我們就多了許多特判的問題，增加了代碼的複雜性。我們再看從下往上走的情況，再看0這個數字，它可以走到他下面的任何兩個4，這就省略了邊界的問題，是以這道題目采用從下到上的方式最為簡單，事實上，這也是這道題目的最優解，同學們做題目做多了自然也就掌握了。
image-20220707103208777.png
C++實作
#include<bits/stdc++.h>
using namespace std;
const int N = 510;//資料範圍500
int f[N][N];
int n;
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i ++)
for(int j = 0; j <= i; j ++)
scanf("%d", &f[i][j]);
for(int i = n - 1; i >= 0; i --)
for(int j = 0; j <= i; j ++)
f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
printf("%d", f[0][0]);
return 0;
} 複制
注：個人認為下标從0開始更好寫代碼，從1開始也一樣，看個人習慣，這并不影響思路
#include<bits/stdc++.h>
using namespace std;
const int N = 510;//資料範圍500
int f[N][N];
int n;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= i; j ++)
scanf("%d", &f[i][j]);
for(int i = n - 1; i >= 0; i --)
for(int j = 1; j <= i; j ++)
f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
printf("%d", f[1][1]);
return 0;
} 複制
摘花生
題目描述
Hello Kitty想摘點花生送給她喜歡的米老鼠。
她來到一片有網格狀道路的矩形花生地(如下圖)，從西北角進去，東南角出來。
地裡每個道路的交叉點上都有種着一株花生苗，上面有若幹顆花生，經過一株花生苗就能摘走該它上面所有的花生。
Hello Kitty隻能向東或向南走，不能向西或向北走。
問Hello Kitty最多能夠摘到多少顆花生。
image-20220707121926075.png
思路分析
分析：經過經典數字三角形問題，我們很容易就了解了其中相似的思考方式，每個點隻能從左邊來或者從上邊來，也是一個典型的dp問題
image-20220707123137117.png
C++實作
#include <bits/stdc++.h>
using namespace std;
const int N = 110;//資料範圍
int w[N][N], f[N][N];
int n, m;
int main()
{
int T;//T組資料
scanf("%d", &T);
while(T --)
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
scanf("%d", &w[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]) + w[i][j];
printf("%d\n", f[n][m]);
}
return 0;
} 複制
最低通行費
題目描述
一個商人穿過一個 N×NN×N 的正方形的網格，去參加一個非常重要的商務活動。
他要從網格的左上角進，右下角出。
每穿越中間 11 個小方格，都要花費 11 個機關時間。
商人必須在 (2N−1)(2N−1) 個機關時間穿越出去。
而在經過中間的每個小方格時，都需要繳納一定的費用。
這個商人期望在規定時間内用最少費用穿越出去。
請問至少需要多少費用？
注意：不能對角穿越各個小方格（即，隻能向上下左右四個方向移動且不能離開網格）。
思路分析1
分析：經過上面兩道題目的學習，我們很容易發現這道題目是摘花生的進階，本質上差不多，摘花生是求max，最低通行費是求min，分析思路也與上面完全一樣，是以這裡就不畫dp分析了，需要注意的是2n - 1是什麼，很容易分析，如下圖，可以看到不是就是兩個邊長減去1，也就是紅格子，稍微一分析就發現和摘花生完全一樣，隻能從左上角走到右下角，而且每次隻能往右走或者往下走。
image-20220707131405128.png
與摘花生不一樣的最小值怎麼分析，若一味的把上面的代碼照搬下來肯定是錯誤的，原因在這裡，看上面的綠格子，它隻能從左邊來，不能從上邊來，從上邊來的話上邊初始化為0，經過min的運算，肯定是選擇了上面的格子，答案肯定錯，但是摘花生的max就不會出現這種情況。
C++實作1
#include <bits/stdc++.h>
using namespace std;
const int N = 110, INF = 1e9;
int n;
int w[N][N], f[N][N];
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
scanf("%d", &w[i][j]);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
{
if(i == 1 && j == 1) f[i][j] = w[i][j];//對第一個格子特判
else
{
//對于所有的格子，一定能更新，但要注意邊界
f[i][j] = INF;//所有格子初始化最大值
if(i > 1) f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]);//如果不是第一行，可以從上面走下來
if(j > 1) f[i][j] = min(f[i][j], f[i][j - 1] + w[i][j]);//如果不是第一列，可以從下面走下來
}
}
printf("%d", f[n][n]);
return 0;
} 複制
思路分析2
分析：針對思路分析1，我們可以看到代碼描述如上，與摘花生的代碼有些許不同，特判的條件太多，我們還是不希望這樣的事情發生，是以我們針對上面的問題，來一個初始化數組正無窮的操作。
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n;
int w[N][N], f[N][N];
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
scanf("%d", &w[i][j]);
memset(f, 0x3f, sizeof f);//将數組初始化為正無窮
f[1][1] = w[1][1]; //對左上角元素特殊處理
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= n; j ++)
{
f[i][j] = min(f[i][j], f[i][j - 1] + w[i][j]);
f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]);
}
}
printf("%d", f[n][n]);
return 0;
} 複制
ps:最開始初始化我沒有想到memset，我想到的是把f數組都初始化為一個較大的數，但答案是錯誤的，這裡給大家示範一下
#include <bits/stdc++.h>
using namespace std;
const int N = 5;
int main()
{
int f[N] = {4};
for(int i = 0; i < N; i ++)
printf("%d ", f[i]);
return 0;
}
//4 0 0 0 0 複制
我們想把它全部初始化為某一個數，這樣做隻會初始化第一個數，是以如果還是要初始化為某一個數，得用for循環。
方格取數
題目描述
設有 N×N 的方格圖，我們在其中的某些方格中填入正整數，而其它的方格中則放入數字0。如下圖所示：算法競賽動态規劃篇——數字三角形模型經典數字三角形問題摘花生最低通行費方格取數總結 2.gif
某人從圖中的左上角 A 出發，可以向下行走，也可以向右行走，直到到達右下角的 B 點。
在走過的路上，他可以取走方格中的數（取走後的方格中将變為數字0）。
此人從 A 點到 B 點共走了兩次，試找出兩條這樣的路徑，使得取得的數字和為最大。
思路分析
分析：此題與摘花生不同的是走兩次，可以走兩次來進行，走過的将數字重置為0。在這裡我們介紹同時走的方法。
image-20220707163741769.png
這裡要考慮一個問題，這兩個格子是否是同一個格子，如果是，那麼加一個格子，如果不是，那麼兩個格子的數都相加
C++實作
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int w[N][N];
int f[N + N][N][N];
int main()
{
int n;
scanf("%d", &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);
}
}
printf("%d", f[n + n][n][n]);
return 0;
} 複制
我們看到核心部分的代碼過于冗長，可以将其進行簡化
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 15;
int n;
int w[N][N];
int f[2 * N][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];
for(int a = 0; a <= 1; a ++)
for(int b = 0; b <= 1; b++)
x = max(x, f[k - 1][i1 - a][i2 - b] +t);
// x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
// x = max(x, f[k - 1][i1][i2 - 1] + t);
// x = max(x, f[k - 1][i1 - 1][i2] + t);
// x = max(x, f[k - 1][i1][i2] + t);
}
}
printf("%d\n", f[n + n][n][n]);
return 0;
} 複制
總結
數字三角形問題是dp當中一個簡單的模型，我們可以看到取max時，數組初始化0；取min時，數組用memset初始化更優；另外，屬性除了max和min，有時候還會出現數量。