注意事項：
本題為線性dp—數(shù)字三角形的擴(kuò)展題。

題目：
一個商人穿過一個 N×N 的正方形的網(wǎng)格，去參加一個非常重要的商務(wù)活動。
他要從網(wǎng)格的左上角進(jìn)，右下角出。
每穿越中間 1 個小方格，都要花費 1 個單位時間。
商人必須在 (2N?1) 個單位時間穿越出去。
而在經(jīng)過中間的每個小方格時，都需要繳納一定的費用。
這個商人期望在規(guī)定時間內(nèi)用最少費用穿越出去。
請問至少需要多少費用？

注意：不能對角穿越各個小方格（即，只能向上下左右四個方向移動且不能離開網(wǎng)格）。

輸入格式
第一行是一個整數(shù)，表示正方形的寬度 N。
后面 N 行，每行 N 個不大于 100 的正整數(shù)，為網(wǎng)格上每個小方格的費用。

輸出格式
輸出一個整數(shù)，表示至少需要的費用。

數(shù)據(jù)范圍
1≤N≤100

輸入: 5 1 4 6 8 10 2 5 7 15 17 6 8 9 18 20 10 11 12 19 21 20 23 25 29 33 輸出： 109 #include <iostream> #include <cstring>using namespace std; const int N = 110; int n; int a[N][N], f[N][N];int main() {//讀入cin >> n;for (int i = 1; i<=n; i++) {for (int j = 1; j<=n; j++) cin >> a[i][j];}//初始化DP數(shù)組f,使每個元素為最大值,以便后面的計算時比較得出較小的費用for (int i = 0; i<=n; i++) memset(f[i], 0x3f3f3f3f, sizeof f[i]); //線性DPfor (int i = 1; i<=n; i++) {for (int j = 1; j<=n; j++) {if (i == 1 && j == 1) f[1][1] = a[1][1]; //第一個點的費用賦值else {//如果i>1,則可以從上面走過來,比較上面的路徑費用和當(dāng)前路徑費用的大小,并取較小值if (i > 1) f[i][j] = min(f[i-1][j] + a[i][j], f[i][j]);//如果j>1,則可以從左面走過來,比較左面的路徑費用和當(dāng)前路徑費用的大小,并取較小值if (j > 1) f[i][j] = min(f[i][j-1] + a[i][j], f[i][j]);}}}cout << f[n][n] << endl; //輸出最小費用return 0; }

思路：
經(jīng)典的線性dp問題，y式dp分析即可

1.狀態(tài)表示
f[i][j] 表示從起始點到（i, j）點的所有方案費用，屬性為Min

2.狀態(tài)計算
由于有步數(shù)限制（2N-1），意味著我們只能從起始點向下或者向右移動，那么在進(jìn)行dp計算時，對于點（i，j）我們是從這個點的上方和左側(cè)來進(jìn)行計算，也就是：
f[i][j] = Min(f[i-1][j]，f[i][j-1]) + a[i][j]
代碼中根據(jù)這個來進(jìn)行一定的小調(diào)整即可

聲明：
算法思路來源為y總，詳細(xì)請見https://www.acwing.com/
本文僅用作學(xué)習(xí)記錄和交流

總結(jié)

以上是生活随笔為你收集整理的C++---数字三角形模型---最低通行费（每日一道算法2023.1.14）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。