LeetCode 解題筆記：1301. Number of Paths with Max Score

作者：王一哲
日期：2026年7月5日


LeetCode 題目連結：1301. Number of Paths with Max Score

解題想法

困難題。題目給定一個由字串組成的一維陣列 board，代表一張二維地圖，所有的字元皆為數字 1 ~ 9、S、E，其中 S 代表最右下角的起點，E 代表最左上角的終點，數字代表這格的分數。每次移動時可以向上、向左或向左上走一格，題目要找出從右下走到左上可以搜集到的最高總分，以及可以搜集到最高總分的路徑數量對 1000000007 取餘數。
可以用二維動態規畫處理這題。假設 board 的尺寸為 $n \times n$，定義尺寸為 $n \times n$ 的二維陣列 $score$，代表走到指定格子的最高總分，$score$ 全部預設為 $-1$ 代表沒有走到這格，再將起點 $score[n-1][n-1]$ 設為 0。另一個的二維陣列 $path$，代表走到指定格子的路徑數量，$path$ 全部預設為 $0$。接下來用兩層 for 迴圈，從右下往左上填格子，如果遇到 $r = n-1, c = n-1$ 或是 $board[r][c] == 'X'$ 跳過這格，再從右、下、右下這 3 格找出最高的分數及路徑數量，更新 $score[r][c]$ 及 $path[r][c]$。處理完所有的格子之後，如果 $score[0][0] == -1$ 代表無法走到左上角，回傳 $[0, 0]$；如果可以走到終點，回傳 $[score[0][0], path[0][0]$。

Python 程式碼

Runtime: 106 ms, beats 68.81%. Memory: 20.22 MB, beats 58.72%.

class Solution:
    def pathsWithMaxScore(self, board):
        # 二維動態規畫
        MOD = 10**9 + 7
        n = len(board)  # board 尺寸 n*n
        score = [[-1] * n for _ in range(n)]  # 最高分，-1 代表未走到這格
        score[n-1][n-1] = 0  # 初始值為 0
        path = [[0] * n for _ in range(n)]  # 最高分的路徑數量
        path[n-1][n-1] = 1  # 初始值為 1
        
        # 從右下往左上填入數值
        for r in range(n-1, -1, -1):
            for c in range(n-1, -1, -1):
                # 起點或是障礙物，跳過
                if (r == n-1 and c == n-1) or board[r][c] == 'X':
                    continue
                # 找右、下、右下可以走到這格的分數、路徑數
                cands = []  # (prev_score, prev_path)
                if r + 1 < n and score[r+1][c] != -1:  # 下走到上
                    cands.append((score[r+1][c], path[r+1][c]))
                if c + 1 < n and score[r][c+1] != -1:  # 右走到左
                    cands.append((score[r][c+1], path[r][c+1]))
                if r + 1 < n and c + 1 < n and score[r+1][c+1] != -1:  # 右下走到左上
                    cands.append((score[r+1][c+1], path[r+1][c+1]))
                # 如果無法走到這格
                if not cands: continue
                # 如果 cands 有資料，找出之中的最高分及路徑數量
                max_prev_score, total_path = 0, 0
                for prev_score, prev_path in cands:
                    if prev_score > max_prev_score:
                        max_prev_score = prev_score
                        total_path = prev_path
                    elif prev_score == max_prev_score:
                        total_path = (total_path + prev_path) % MOD
                # 更新這格的最高分、路徑數量
                val = 0
                if board[r][c] != 'E': val = int(board[r][c])
                score[r][c] = val + max_prev_score
                path[r][c] = total_path
        # 如果無法走到 (0, 0) 回傳 [0, 0]
        if score[0][0] == -1:
            return [0, 0]
        else:  # 可以走到 (0, 0)，回傳 [最高分, 路徑數量]
            return [score[0][0], path[0][0]]

C++ 程式碼

Runtime: 43 ms, beats 26.48%. Memory: 30.23 MB, beats 21.25%.

class Solution {
public:
    vector<int> pathsWithMaxScore(vector<string>& board) {
        const int MOD = 1000000007;
        int n = (int)board.size();  // 尺寸 n*n
        // 初始化二維動態規畫用的陣列
        vector<vector<long>> score (n, vector<long> (n, -1)), path (n, vector<long> (n, 0));
        score[n-1][n-1] = 0;
        path[n-1][n-1] = 1;
        // 二維動態規畫，從右下往左上填格子
        for(int r = n-1; r >= 0; r--) {
            for(int c = n-1; c >= 0; c--) {
                // 右下角或這格是障礙物，跳過
                if ((r == n-1 && c == n-1) || board[r][c] == 'X') {
                    continue;
                }
                // 找下、右、右下可能走到這格的最高分數及路徑數量
                vector<pair<long, long>> cands;
                if (r+1 < n && score[r+1][c] != -1) {
                    cands.push_back({score[r+1][c], path[r+1][c]});
                }
                if (c+1 < n && score[r][c+1] != -1) {
                    cands.push_back({score[r][c+1], path[r][c+1]});
                }
                if (r+1 < n && c+1 < n && score[r+1][c+1] != -1) {
                    cands.push_back({score[r+1][c+1], path[r+1][c+1]});
                }
                // 無法走到這格，跳過
                if (cands.empty()) continue;
                // 找出走到這格的最高分、路徑數量
                long max_prev_score = 0, total_path = 0;
                for(auto it : cands) {
                    if (it.first > max_prev_score) {
                        max_prev_score = it.first;
                        total_path = it.second;
                    } else if (it.first == max_prev_score) {
                        total_path = (total_path + it.second) % MOD;
                    }
                }
                long val = 0;
                if (board[r][c] != 'E') val = board[r][c] - '0';
                score[r][c] = val + max_prev_score;
                path[r][c] = total_path;
            }
        }
        // 如果無法走到 (0, 0)，回傳 {0, 0}
        if (score[0][0] == -1) {
            return {0, 0};
        } else {  // 如果可以走到 (0, 0)，回傳最高分及路徑數量
            return {(int)score[0][0], (int)path[0][0]};
        }
    }
};