三维动态规划-LeetCode3418. 机器人可以获得的最大金币数

太爽了！做完这道题，让我感觉就像是斩杀了一条大龙！历时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 = 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 #include #include 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 = 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(mnegativeMostMax=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); //矩阵拓展.存储money for(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;}

感谢大家的观看和喜欢！祝读者朋友们也屠龙痛快！

丽江小吃城