14:T518,class Solution { public: int maxPathScore(vector>& grid, int k) { int m = grid.size(), n = grid[0].size(); vector>> dp(m, vector>(n, vector(k + 1, -1))); dp[0][0][0] = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { for (int c = 0; c <= k; c++) { if (dp[i][j][c] == -1) continue; if (i + 1 < m) { int val = grid[i + 1][j]; int cost = (val == 0) ? 0 : 1; if (c + cost <= k) { dp[i + 1][j][c + cost] = max(dp[i + 1][j][c + cost], dp[i][j][c] + val); } } if (j + 1 < n) { int val = grid[i][j + 1]; int cost = (val == 0) ? 0 : 1; if (c + cost <= k) { dp[i][j + 1][c + cost] = max(dp[i][j + 1][c + cost], dp[i][j][c] + val); } } } } } int ans = -1; for (int c = 0; c <= k; c++) ans = max(ans, dp[m - 1][n - 1][c]); return ans; } };15:T4d3,/** * @param {number[][]} grid * @param {number} k * @return {number} */ var maxPathScore = function(grid, k) { const m = grid.length, n = grid[0].length; const dp = Array(m).fill(0).map(() => Array(n).fill(0).map(() => Array(k + 1).fill(-1))); dp[0][0][0] = 0; for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { for (let c = 0; c <= k; c++) { if (dp[i][j][c] === -1) continue; if (i + 1 < m) { let val = grid[i + 1][j]; let cost = val === 0 ? 0 : 1; if (c + cost <= k) { dp[i + 1][j][c + cost] = Math.max(dp[i + 1][j][c + cost], dp[i][j][c] + val); } } if (j + 1 < n) { let val = grid[i][j + 1]; let cost = val === 0 ? 0 : 1; if (c + cost <= k) { dp[i][j + 1][c + cost] = Math.max(dp[i][j + 1][c + cost], dp[i][j][c] + val); } } } } } let ans = -1; for (let c = 0; c <= k; c++) ans = Math.max(ans, dp[m - 1][n - 1][c]); return ans; };

Time Complexity

Space Complexity