class Solution:
def getMaximumNumber(self, moles: List[List[int]]) -> int:
moles.sort(key = lambda x:x[0])
n = len(moles)
# dp[i][j]表示当我们遇见第i个地鼠时,且锤子位置在j时能够打到的最大地鼠个数,
dp = [[-float('inf') for _ in range(9)] for _ in range(n + 1)]
dp[0][4] = 0
pre = 0
d = [[0 for _ in range(9)] for _ in range(9)]
for i in range(9):
for j in range(9):
d[i][j] = abs(i // 3 - j // 3) + abs(i % 3 - j % 3)
for i in range(1,n + 1):
t,x,y = moles[i - 1]
diff = t - pre
pre = t
for last in range(9):
for next_ in range(9):
if d[last][next_] <= diff:
dp[i][next_] = max(dp[i][next_],dp[i - 1][last])
dp[i][x * 3 + y] += 1
return max(dp[-1])
class Solution {
public int getMaximumNumber(int[][] m) {
//按时间排序
Arrays.sort(m, Comparator.comparingInt((a)->(a[0])));
//拷贝一份数组m，把起始位置（0，1，1）考虑进去。arraycopy还挺慢的，伙计们可以换别的实现
int[][] q = new int [m.length + 1][3];
System.arraycopy(m, 0, q, 1, m.length);
q[0] = new int[] {0, 1, 1};
// dp[i][0] 表示前 i 只地鼠中，第 i 只地鼠不打的情况下，获得的最大分数。
// dp[i][1]表示前 i 只地鼠中，第 i 只地鼠打的情况下，获得的最大分数。
int[][] dp = new int[q.length][2];
// i 可以从1开始遍历，因为在dp[0][0]和dp[0][1]的值为0；
for(int i = 1; i < q.length; i++){
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
//假如无法从0状态（初始状态）到达i状态（当前状态），则dp[i][1]=0;
if(!time(q, i, 0)) continue;
for(int j = i - 1; j >= 0; j--){
//time函数用来判断j能否到达i;
if(time(q, i, j)){
dp[i][1]=Math.max(dp[j][1] + 1, dp[i][1]);
}
//相差4打破循环。
if(q[i][0] - q[j][0] >= 4){
dp[i][1]=Math.max(dp[j][0] + 1, dp[i][1]);
break;
}
}
}
return (int)Math.max(dp[m.length][0], dp[m.length][1]);
}
boolean time(int[][] m, int i, int j){
int t = m[i][0] - m[j][0];
int need = Math.abs(m[i][1] - m[j][1]) + Math.abs(m[i][2] - m[j][2]);
return need <= t;
}
}
{:height="200px"}
勇者面前有一个大小为