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

发布于：2025-03-31 ⋅ 阅读:(19) ⋅ 点赞:(0)

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

 

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

 

 

 

 

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布