美团后端3月11日第二题,求有什么坑

wo是完全不懂为啥只过了45%
  for(int i=1;i<=n;++i){
    for(int j=1;j<=m;++j){   
      dp[i][j]=-1;//初始化为-1
    if(i==1&&j==1){
    dp[i][j]=a[i][j];
    continue;
    }
      if(i-1>=1&&dp[i-1][j]>=0){//可以转移
        if(s[i-1][j]==s[i][j]){//相同
          dp[i][j]=max(dp[i-1][j]+a[i][j],dp[i][j]);
        }
        if(s[i-1][j]!=s[i][j]&&dp[i-1][j]-k>=0){//不相同
          dp[i][j]=max(dp[i-1][j]+a[i][j]-k,dp[i][j]);
        }
      }
      if(j-1>=1&&dp[i][j-1]>=0){//可以转移的必要条件
        if(s[i][j-1]==s[i][j]){//相同
          dp[i][j]=max(dp[i][j],dp[i][j-1]+a[i][j]);
        }
        if(s[i][j-1]!=s[i][j]&&dp[i][j-1]-k>=0){//不相同
          dp[i][j]=max(dp[i][j],dp[i][j-1]+a[i][j]-k);
        }
      }
      ans=max(ans,dp[i][j]);//更新结果
    }
  }
全部评论
咱两写的一样
点赞 回复 分享
发布于 2023-03-11 21:11 浙江
差不多一样的思路 我也只能45
点赞 回复 分享
发布于 2023-03-11 21:12 江苏
一样,也是45
点赞 回复 分享
发布于 2023-03-11 21:13 上海
你是不是没判断走不了的情况,如果dp[i-i][j]和dp[i][j-1]都小于k且与dp[i][j]异色的话,就强制结束了
点赞 回复 分享
发布于 2023-03-11 21:15 湖北
说是把dp[1][1]强制为0就过了
点赞 回复 分享
发布于 2023-03-11 21:34 北京
一样45
点赞 回复 分享
发布于 2023-03-11 21:35 广东
f[i][j] 要初始化为 -INF,-1可不够,会走到实际走不到的地方
点赞 回复 分享
发布于 2023-03-11 21:36 上海
你要判断用来转移的前一个 dp[i][j-1] 是否为 -1,是 -1 就不能转移 不然的话,如果 (i, j-1) 和当前格子颜色相同,而 dp[i][j-1] + a[i][j] > 0,那么这样会更新你的 dp[i][j],而实际 dp[i][j-1] = -1 代表 (i,j-1) 是不能走到的,也就不能从 (i ,j-1) 走到 (i, j)
点赞 回复 分享
发布于 2023-03-11 21:39 湖北
他从左上角的0开始一直有异色>=0的判断dp元素咋会是负值捏
点赞 回复 分享
发布于 2023-03-11 21:47 江苏
奇怪,我跟你差不多,我通过全部案例了,我看了半天也不知道我的跟你的哪里差很多
点赞 回复 分享
发布于 2023-03-11 22:37 广东

相关推荐

头像
09-29 16:18
门头沟学院 Java
点赞 评论 收藏
分享
3 收藏 评论
分享
牛客网
牛客企业服务