14:T540,class Solution { public: vector pathsWithMaxScore(vector& board) { int n = board.size(); vector>> dp(n, vector>(n, {-1, 0})); dp[n - 1][n - 1] = {0, 1}; int mod = 1e9 + 7; vector> dirs = {{1, 0}, {0, 1}, {1, 1}}; for (int i = n - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { if (i == n - 1 && j == n - 1) continue; if (board[i][j] == 'X') continue; for (auto& d : dirs) { int r = i + d.first, c = j + d.second; if (r < n && c < n && dp[r][c][0] != -1) { if (dp[r][c][0] > dp[i][j][0]) { dp[i][j][0] = dp[r][c][0]; dp[i][j][1] = dp[r][c][1]; } else if (dp[r][c][0] == dp[i][j][0]) { dp[i][j][1] = (dp[i][j][1] + dp[r][c][1]) % mod; } } } if (dp[i][j][0] != -1 && board[i][j] != 'E') { dp[i][j][0] += board[i][j] - '0'; } } } return dp[0][0][0] == -1 ? vector{0, 0} : vector{dp[0][0][0], dp[0][0][1]}; } };15:T48f,var pathsWithMaxScore = function(board) { const n = board.length; const dp = Array.from({ length: n }, () => Array.from({ length: n }, () => [-1, 0]) ); dp[n - 1][n - 1] = [0, 1]; const mod = 1e9 + 7; const dirs = [[1, 0], [0, 1], [1, 1]]; for (let i = n - 1; i >= 0; i--) { for (let j = n - 1; j >= 0; j--) { if (i === n - 1 && j === n - 1) continue; if (board[i][j] === 'X') continue; for (const [di, dj] of dirs) { const r = i + di, c = j + dj; if (r < n && c < n && dp[r][c][0] !== -1) { if (dp[r][c][0] > dp[i][j][0]) { dp[i][j][0] = dp[r][c][0]; dp[i][j][1] = dp[r][c][1]; } else if (dp[r][c][0] === dp[i][j][0]) { dp[i][j][1] = (dp[i][j][1] + dp[r][c][1]) % mod; } } } if (dp[i][j][0] !== -1 && board[i][j] !== 'E') { dp[i][j][0] += parseInt(board[i][j]); } } } return dp[0][0][0] === -1 ? [0, 0] : [dp[0][0][0], dp[0][0][1]]; };

Time Complexity

Space Complexity