美团后端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]);//更新结果
}
}
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]);//更新结果
}
}
全部评论
咱两写的一样
差不多一样的思路 我也只能45
一样,也是45
你是不是没判断走不了的情况,如果dp[i-i][j]和dp[i][j-1]都小于k且与dp[i][j]异色的话,就强制结束了
说是把dp[1][1]强制为0就过了
一样45
f[i][j] 要初始化为 -INF,-1可不够,会走到实际走不到的地方
你要判断用来转移的前一个 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)
他从左上角的0开始一直有异色>=0的判断dp元素咋会是负值捏
奇怪,我跟你差不多,我通过全部案例了,我看了半天也不知道我的跟你的哪里差很多
相关推荐