太爽了！做完這道題，讓我感覺就像是斬殺了一條大龍！歷時72天，分3次花掉30小時。終獲突破！

零、題目

3418. 機器人可以獲得的最大金幣數

給你一個?m x n?的網格。一個機器人從網格的左上角?(0, 0)?出發，目標是到達網格的右下角?(m - 1, n - 1)。在任意時刻，機器人只能向右或向下移動。

網格中的每個單元格包含一個值?coins[i][j]：

• 如果?coins[i][j] >= 0，機器人可以獲得該單元格的金幣。
• 如果?coins[i][j] < 0，機器人會遇到一個強盜，強盜會搶走該單元格數值的?絕對值?的金幣。

機器人有一項特殊能力，可以在行程中?最多感化?2個單元格的強盜，從而防止這些單元格的金幣被搶走。

注意：機器人的總金幣數可以是負數。

返回機器人在路徑上可以獲得的?最大金幣數?。

一、思路誕生

最開始沒有思路。對于動態規劃做了很多題。

動態規劃現在總結為五大步：

0.從(0,0)之類的挪到(1,1)方便使用

1.確定能影響結果的自變量

2.定義一個dp，當然可以是多元函數。C語言支持多維數組。

給出dp[i][j]的含義。用中文

3.寫出狀態轉移方程。根據最后一個，通常是最后一個，或者右下角

4.求解結果：取出最后一個（或者最后一疊）中的最值。

二、本題思路

由于讀完題后，發現這里有幾個關鍵的自變量。

一個是二維數組的坐標(m,n)

另一個是使用感化的次數k

由于金幣相當于是已知信息，并且這個信息不受其他信息的影響是絕對不變的。

而要求解問題時，某個具體坐標的具體感化次數都是會受到影響的。

倘若沒有感化次數，也就是每資格感化，絕對不變，也就是不受其他信息的影響，那就沒必要使用動態規劃函數里面的一個變量。

于是就開始寫狀態轉移方程

dp(m,n,k)表示從(1,1)到(m,n)恰好使用k次感化所能獲得的最大金幣數。（到4.得到結果那里發現這個定義不夠準確，但是狀態轉移方程那里倒是對了）

當然也可以用別的方式定義，但是狀態方程會變化。這種我自己覺得比價好想。

而后就是從k=0開始考量，一點一點考量。k=1開始考量。一點一點的。

最后想出了狀態轉移方程的全部（見草稿紙）

然后中間有一點卡住了，就是一直在想這一格是感化還是不感化呢。后來看了題干，恍然大悟，大于等于0的時候，根本不能感悟。只有小于0的時候才能感悟。于是，就應該根據這個格子金幣是否小于0做出判斷。

?

三、開始寫代碼

分為四部分：數據讀入并遷移、數據初始化、狀態轉移、得到結果

1.數據讀入并遷移

力扣里面int maximumAmount(int** coins, int coinsSize, int* coinsColSize)的含義就是

數組，行長度（有多少行），列長度（有多少列）

int extGrid[600][600];int i, j, k;int m = coinsSize; int n = *coinsColSize;for (i = 0; i < m; i++) {for (j = 0; j < n; j++) {extGrid[i + 1][j + 1] = coins[i][j];//printf("%d ",coins[i][j]);}}for (i = 1; i <= m; i++) {for (j = 1; j <= n; j++) {printf("%d ", extGrid[i][j]);}puts("");}

這樣就可以完成遷移并打印檢查了。

2.數據初始化

數據初始化就是考慮第0行和第0列。這是一個常規操作。但是由于這里金幣范圍是[-1000,1000]設置一個負無窮什么的就可以。但是我這里做了一小點創新。就是我使用了一種自定義的最大值獲取，我稱為Emax，存在最大值existMax。因為狀態轉移方程里面，會看到如果這種情況不存在的話，那就不用考慮。而最后放入dp格子中時，肯定要加入extGrid[i][j]，那么這些不存在的情況其實就是0.所以來看一下Emax的實現

int isAlive(int mem[3]) {int r = mem[0];int q = mem[1];if (r == 0) {return 0;}if (q == 0) {return 0;}return 1;
}
int getNum(int mem[3]) {int r = mem[0];int q = mem[1];int s = mem[2];return dp[r][q][s];
}
int Emax(int mem1[3], int mem2[3]) {int ali1 = isAlive(mem1);int ali2 = isAlive(mem2);if (!ali1&&!ali2) {return 0;//都不存在，該值為0}if (!ali1 && ali2) {return getNum(mem2);}if (ali1 && !ali2) {return getNum(mem1);}//都存在，返回較大的return fmax(getNum(mem1), getNum(mem2));
}

3.狀態轉移

這一步的關鍵就是準確列出所有情況。分類討論。

這里有兩點創新。

一個是因為每次寫dp[i][j][k]挺累的，不妨弄一個member成員，用來方便書寫。每次只要傳member就可以了。另外就是可以看到先用Emax取存在的結果，再用Emax得到的結果使用庫函數fmax取最大值得到結果。

for (i = 1; i <= m; i++) {for (j = 1; j <= n; j++) {if (extGrid[i][j] >= 0) {for (k = 0; k <= 2; k++) {int mem1[3] = { i - 1,j,k };int mem2[3] = { i,j - 1,k };dp[i][j][k] = Emax(mem1, mem2)+extGrid[i][j];}}else {//dp(m,n,0)k = 0;int mem1[3] = { i - 1,j,k };int mem2[3] = { i,j - 1,k };dp[i][j][k] = Emax(mem1, mem2) + extGrid[i][j];//dp(m,n,1)k = 1;int bmem1[3] = { i - 1,j,k };int bmem2[3] = { i,j - 1,k };k = 0;int bmem3[3] = { i - 1,j,k };int bmem4[3] = { i,j - 1,k };int t1= Emax(bmem1, bmem2) + extGrid[i][j];int t2 = Emax(bmem3, bmem4);k = 1;dp[i][j][k] = fmax(t1,t2) ;//dp(m,n,2)k = 2;int cmem1[3] = { i - 1,j,k };int cmem2[3] = { i,j - 1,k };k = 1;int cmem3[3] = { i - 1,j,k };int cmem4[3] = { i,j - 1,k };t1 = Emax(cmem1, cmem2) + extGrid[i][j];t2 = Emax(cmem3, cmem4);k = 2;dp[i][j][k] = fmax(t1, t2);}}}

4.得到結果

這里就只需要取最后的位置，摘取勝利果實就可以了。

return fmax(fmax(dp[m][n][0], dp[m][n][1]), dp[m][n][2]);

不過，需要注意的是，感化次數為2，自然一定比恰使用感化次數為1的金幣數多。因為多一次機會。不過是否每次都能有2次感化的機會呢？需要得有2個負數才可以。否則2次感化就是抄的之前的結果。如果之前一直為0的話。那就出故障了。所以還是應該fmax最好。不過巧了。這里沒有影響。因為實際上我們實現的代碼dp的含義是，感化次數最多為k的時候，所能得到的最大金幣數量。這樣狀態轉移方程才合理。

四、提交改BUG

0.本地vs2022調試失敗

出現棧溢出錯誤。上網學習，發現改一下就好了。

dp[600][600][3]這是數組，肯定是在棧上的。

如果用malloc，就會在堆上，但是會很麻煩。

感謝下面的博客教我計算。格子里的數字單位是字節。差不多10MB的內存能跑起來，100MB或者200MB肯定就夠用了

VS運行時報錯：未經處理的異常-CSDN博客???????

修好啦！

1.小于等于號漏等于

分類討論那里。就需要注意不能只是小于。只小于最后的結果，就是輸出的k=0，k=1全部都是0.用調試，調了一下感覺沒那么方便但是有一些一調試就是一下就能看出來。其實還是看調試那里，感覺監視窗口里面i,j,k的值不變，就哪里有問題哪里打斷點，比較快地解決了。

2.在372個測試樣例時出現了超時

一交，對了300多個。我很激動。說明算法對了。哪里還需要小小優化一下。

一種是算法不是最快的，但是我這O(N^2)已經最快了。不是這個原因

另一種是差個系數。我覺得是這個。

①首先調整了isAlive代碼嘗試變快

收效甚微

②其次問chatGLM智譜清言

告訴我了這個。我覺得ptintf這個I/O輸出很有道理（下圖第4條），就試了一下。

結果沒想到從790ms一下子變成了27ms，快了將近30倍。我的媽呀。

這個一改。就過了。

五、完整代碼

通關截圖：

#include <stdio.h>
#include <malloc.h>
#include <math.h>
int dp[600][600][3];//0,1,2表示感化次數
int isAlive(int mem[3]) {int r = mem[0];int q = mem[1];if (r == 0) {return 0;}if (q == 0) {return 0;}return 1;
}
int getNum(int mem[3]) {int r = mem[0];int q = mem[1];int s = mem[2];return dp[r][q][s];
}
int Emax(int mem1[3], int mem2[3]) {int ali1 = isAlive(mem1);int ali2 = isAlive(mem2);if (!ali1&&!ali2) {return 0;//都不存在，該值為0}if (!ali1 && ali2) {return getNum(mem2);}if (ali1 && !ali2) {return getNum(mem1);}//都存在，返回較大的return fmax(getNum(mem1), getNum(mem2));}
int maximumAmount(int** coins, int coinsSize, int* coinsColSize) {int extGrid[600][600];int i, j, k;int m = coinsSize; int n = *coinsColSize;for (i = 0; i < m; i++) {for (j = 0; j < n; j++) {extGrid[i + 1][j + 1] = coins[i][j];//printf("%d ",coins[i][j]);}}for (i = 1; i <= m; i++) {for (j = 1; j <= n; j++) {printf("%d ", extGrid[i][j]);}puts("");}for (i = 1; i <= m; i++) {for (j = 1; j <= n; j++) {if (extGrid[i][j] >= 0) {for (k = 0; k <= 2; k++) {int mem1[3] = { i - 1,j,k };int mem2[3] = { i,j - 1,k };dp[i][j][k] = Emax(mem1, mem2)+extGrid[i][j];}}else {//dp(m,n,0)k = 0;int mem1[3] = { i - 1,j,k };int mem2[3] = { i,j - 1,k };dp[i][j][k] = Emax(mem1, mem2) + extGrid[i][j];//dp(m,n,1)k = 1;int bmem1[3] = { i - 1,j,k };int bmem2[3] = { i,j - 1,k };k = 0;int bmem3[3] = { i - 1,j,k };int bmem4[3] = { i,j - 1,k };int t1= Emax(bmem1, bmem2) + extGrid[i][j];int t2 = Emax(bmem3, bmem4);k = 1;dp[i][j][k] = fmax(t1,t2) ;//dp(m,n,2)k = 2;int cmem1[3] = { i - 1,j,k };int cmem2[3] = { i,j - 1,k };k = 1;int cmem3[3] = { i - 1,j,k };int cmem4[3] = { i,j - 1,k };t1 = Emax(cmem1, cmem2) + extGrid[i][j];t2 = Emax(cmem3, cmem4);k = 2;dp[i][j][k] = fmax(t1, t2);}}}for (k = 0; k <= 2; k++) {printf("k is %d\n", k);for (i = 1; i <= m; i++) {for (j = 1; j <= n; j++) {//printf("dp[%d][%d][%d]=%d\n", i, j, k, dp[i][j][k]);printf("%d ", dp[i][j][k]);}puts("");}}return fmax(fmax(dp[m][n][2], dp[m][n][1]), dp[m][n][2]);
}
int main() {int* arr1 = (int*)malloc(sizeof(int) * 3);int *arr2= (int*)malloc(sizeof(int) * 3);int* arr3 = (int*)malloc(sizeof(int) * 3);int coins2 [3][3] = {{0, 1, -1},{1, -2, 3},{2, -3, 4}};int** coins = (int**)malloc(sizeof(int*) * 3);coins[0] = arr1; coins[1] = arr2; coins[2] = arr3;int i, j;for (i = 0; i < 3; i++) {for (j = 0; j < 3; j++) {coins[i][j] = coins2[i][j];}}int col = 3;int ans = maximumAmount(coins,3,&col);printf("\nans is %d\n", ans);return 0;
}

補負一、失敗的思路

因為代碼太復雜，寫初始化卡死了。初始化想不通。

失敗的代碼。從失敗中獲得了啟發。想到了Emax函數
typedef struct Square{int a0;int a1;int a2;int negativeMostMax;int negativeSecondMax;int money;
}sq;
int fmaxnum(int a, int b){if(a==b){return 3;}if(a>b){return 1;}return 2;
}
void changeNegative(sq lastSq,sq * square){int min1=lastSq.negativeMostMax;int min2=lastSq.negativeSecondMax;int m=square->money;if(m<min1){min2=min1;min1=m;}else if(m<min2){min2=m;}square->negativeMostMax=min1;square->negativeSecondMax=min2;
}
void showSquareArr(sq sqArr[600][600],int m,int n){puts("");puts("k=0");int i,j;for(i=0;i<=m;i++){for(j=0;j<=n;j++){printf("%d ",sqArr[i][j].a0);}puts("");}puts("");puts("");puts("negativeMostMax");for(i=0;i<=m;i++){for(j=0;j<=n;j++){printf("%d ",sqArr[i][j].negativeMostMax);}puts("");}puts("");puts("");puts("negativeSecondMax");for(i=0;i<=m;i++){for(j=0;j<=n;j++){printf("%d ",sqArr[i][j].negativeSecondMax);}puts("");}puts("");// puts("");// puts("k=1");// for(i=0;i<=m;i++){//     for(j=0;j<=n;j++){//         printf("%d ",sqArr[i][j].a1);//     }//     puts("");// }// puts("");// puts("");// puts("k=2");// for(i=0;i<=m;i++){//     for(j=0;j<=n;j++){//         printf("%d ",sqArr[i][j].a2);//     }//     puts("");// }// puts("");// puts("");// puts("moneyGrid");// for(i=0;i<=m;i++){//     for(j=0;j<=n;j++){//         printf("%d ",sqArr[i][j].money);//     }//     puts("");// }// puts("");}int maximumAmount(int** coins, int coinsSize, int* coinsColSize) {int i,j;int i_,j_;sq extGrid[600][600]={9};//11：10開始思考//11:20有思路，開始驗證//11：20-11：40更新思路，開始碼代碼//13；13 了解leetcode規則//1413開始碼字int m=coinsSize;int n=*coinsColSize;//showSquareArr(extGrid,m,n);//矩陣拓展.存儲moneyfor(i=0,i_=1;i<m;i++,i_++){for(j=0,j_=1;j<n;j++,j_++){extGrid[i_][j_].money=coins[i][j];}}//showSquareArr(extGrid,m,n);//進行矩陣初始化。（k=0）extGrid[1][1].a0=extGrid[1][1].money;//初始化第一列j=1;for(i=2;i<=m;i++){extGrid[i][j].a0=extGrid[i-1][j].a0+extGrid[i][j].money;}//初始化第一行i=1;for(j=2;j<=n;j++){extGrid[i][j].a0=extGrid[i][j-1].a0+extGrid[i][j].money;}//狀態轉移for(i=2;i<=m;i++){for(j=2;j<=n;j++){extGrid[i][j].a0=fmax(extGrid[i][j-1].a0,extGrid[i-1][j].a0)+extGrid[i][j].money;}}//進行矩陣初始化。（最小值的建立）extGrid[1][1].negativeMostMax=extGrid[1][1].money;//注意第一行第一列只有一個有效值。第一行第二列有2個有效值int mt;mt=extGrid[1][2].money;if(mt<extGrid[1][1].negativeMostMax){extGrid[1][2].negativeSecondMax=extGrid[1][1].negativeMostMax;extGrid[1][2].negativeMostMax=mt;}else{extGrid[1][2].negativeMostMax=extGrid[1][1].negativeMostMax;extGrid[1][2].negativeSecondMax=mt;}//初始化第一行.j從3開始i=1;for(j=3;j<=n;j++){changeNegative(extGrid[i][j-1],&extGrid[i][j]);}//注意第一行第一列只有一個有效值。第二行第一列有2個有效值mt=extGrid[2][1].money;if(mt<extGrid[1][1].negativeMostMax){extGrid[2][1].negativeSecondMax=extGrid[1][1].negativeMostMax;extGrid[2][1].negativeMostMax=mt;}else{extGrid[2][1].negativeMostMax=extGrid[1][1].negativeMostMax;extGrid[2][1].negativeSecondMax=mt;}//初始化第一列.i從3開始j=1;for(i=3;i<=m;i++){changeNegative(extGrid[i-1][j],&extGrid[i][j]);}//狀態轉移for(i=2;i<=m;i++){for(j=2;j<=n;j++){int num=fmaxnum(extGrid[i][j-1].a0,extGrid[i-1][j].a0);extGrid[i][j].a0=fmax(extGrid[i][j-1].a0,extGrid[i-1][j].a0)+extGrid[i][j].money;}}showSquareArr(extGrid,m,n);return 0;
}

?

感謝大家的觀看和喜歡！祝讀者朋友們也屠龍痛快！

?

?

?

?