机器人可以获得的最大金币数
机器人可以获得的最大金币数
题目描述1
题目讲解
定义 dp[i][j][k] = 到达(i,j)并且用了k次无效化时的最大金币.
机器人从左上角走到右下角，只能：向右或者向下.
假设前一个状态是dp_prev,当前格子的值是 c = coins[i][j].
分两种情况讨论: 不使用无效化和可以使用无效化.
- 不使用无效化
dp[i][j][k] = max(dp[i][j][k], dp_prev + c)
- 可以使用无效化
dp[i][j][k+1] = max(dp[i][j][k+1], dp_prev)
初始化: 起点也可能是负数.
不使用无效化: dp[0][0][0] = coins[0][0].
使用无效化: dp[0][0][1] = 0.
最终答案:
max(dp[m-1][n-1][0], dp[m-1][n-1][1], dp[m-1][n-1][2])
代码
c++
python
go
class Solution:
def maximumAmount(self, coins):
m, n = len(coins), len(coins[0])
# 用一个极小的整数表示“不可达状态”，避免干扰 DP 的最大值计算
NEG = -10**18
# dp[i][j][k]：到达 (i,j) 且用了 k 次无效化时的最大金币
dp = [[[NEG] * 3 for _ in range(n)] for __ in range(m)]
# 初始化起点 (0,0)
c0 = coins[0][0]
if c0 >= 0:
dp[0][0][0] = c0
else:
dp[0][0][0] = c0 # 不用无效化
dp[0][0][1] = 0 # 用一次无效化
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
continue
c = coins[i][j]
for k in range(3):
best_prev = NEG
if i > 0:
best_prev = max(best_prev, dp[i-1][j][k])
if j > 0:
best_prev = max(best_prev, dp[i][j-1][k])
if best_prev == NEG:
continue
# 1) 不用无效化，正常加上 c
dp[i][j][k] = max(dp[i][j][k], best_prev + c)
# 2) 如果是负数格子且还能用无效化
if c < 0 and k < 2:
dp[i][j][k+1] = max(dp[i][j][k+1], best_prev)
return max(dp[m-1][n-1])