Leetcode每日一题 —— 1301. 最大得分的路径数目

魔法师 2026-07-05 09:44 1

思路

还挺明显的动规/递推题。本来是想用动规，写成了递推，不过实际思路都一样。

递推的话就是从左上先行后列遍历，推导出从当前格到右、下、右下三个格子的得分，取最大得分对计数进行赋值或累加。推到右下的格子即可。

动规的话就是初始化第一行，设max=Max(f(i-1,j),f(i,j-1),f(i-1,j-1))，那么状态方程就是f(i,j)=max+cnt(max)。

代码

class Solution {

    int[][] grid;

    public int[] pathsWithMaxScore(List<String> board) {

        int n = board.size();

        grid = new int[n][n];

        int[][] dp = new int[n][2];

        for (int i = 0; i < n; i++) {

            String row = board.get(i);

            for (int j = 0; j < n; j++) {

                char chr = row.charAt(j);

                switch (chr) {

                    case 'X', 'E' -> grid[i][j] = Integer.MIN_VALUE;

                    case 'S' -> grid[i][j] = 0;

                    default -> grid[i][j] = row.charAt(j) - '0';

                }

            }

        }

        dp[0][1] = 1;

        for (int j = 1; j < n; j++) {

            dp[j][0] = Integer.MIN_VALUE;

        }

        for (int i = 0; i < n; i++) {

            int[][] next = new int[n][2];

            for (int j = 0; j < n; j++) {

                next[j][0] = Integer.MIN_VALUE;

            }

            for (int j = 0; j < n; j++) {

                if (dp[j][0] == Integer.MIN_VALUE) {

                    continue;

                }

                if (i < n - 1) {

                    updateCell(next, i + 1, j, dp[j]);

                    if (j < n - 1) {

                        updateCell(next, i + 1, j + 1, dp[j]);

                    }

                }

                if (j < n - 1) {

                    updateCell(dp, i, j + 1, dp[j]);

                }

            }

            if (i < n - 1) {

                dp = next;

            }

        }

        if (dp[n - 1][0] == Integer.MIN_VALUE) {

            return new int[] {0, 0};

        }

        return dp[n - 1];

    }

    private void updateCell(int[][] dp, int r, int c, int[] curr) {

        if (grid[r][c] == Integer.MIN_VALUE) {

            return;

        }

        int score = curr[0] + grid[r][c];

        if (dp[c][0] < score) {

            dp[c][0] = score;

            dp[c][1] = 0;

        }

        if (dp[c][0] == score) {

            dp[c][1] = (dp[c][1] + curr[1]) % 1000000007;

        }

    }

}

最新回复 (5)

九只猫 07-05 09:47

1楼

大佬的日常和我的日常，果然之间隔了好几个银河

SomeBottle 07-05 10:22

2楼

虽然还是路径，但是比较典型的二维动态规划题了。

递推最大得分这个是老生常谈了，这题在这个基础上还要统计最大得分的方案。其实就是在每一步递推时，看三条来路有几条并列最大，累加他们的方案数。额外再开个二维递推数组跟着递推方案数即可。

class Solution {

public:

    vector<int> pathsWithMaxScore(vector<string>& board) {

        // 可以向左上三个方向移动，也就是一个格子可能转移自右边、下边或者右下角

        // 找的是代价最大的路径，而且这种路径可能有多条

        // 可以用动态规划

        int n=board.size();

        // dpS 递推最大值，dpM 递推最大值的方案数量

        vector<vector<int>> dpS(n,vector<int>(n,0));

        vector<vector<long long>> dpM(n,vector<long long>(n,0));

        dpM[n-1][n-1]=1; // 位于 S 算一个方案

        int drcts[][2]={

            {1,0},

            {0,1},

            {1,1},

        };

        int modulus=(int)(1e9+7);

        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'){

                    // 遇到障碍了

                    dpS[i][j]=0; // 此处最大值归零

                    dpM[i][j]=0; // 方案数也归零

                }else{

                    int maxVal=-1;

                    long long mCnt=0; // 方案数

                    for(auto& d:drcts){

                        int prevI=i+d[0],prevJ=j+d[1];

                        if(prevI>=n||prevJ>=n||dpM[prevI][prevJ]==0){

                            // 越界或者格子不可达，就忽略

                            continue;

                        }

                        if(dpS[prevI][prevJ]>maxVal){

                            maxVal=dpS[prevI][prevJ];

                            mCnt=dpM[prevI][prevJ];

                        }else if(dpS[prevI][prevJ]==maxVal){

                            mCnt+=dpM[prevI][prevJ];

                        }

                    }

                    if(mCnt==0){

                        // 此处不可达

                        dpS[i][j]=0;

                        dpM[i][j]=0;

                    }else{

                        dpS[i][j]=maxVal;

                        if(board[i][j]!='E'){

                            // 不是终点就是数字

                            dpS[i][j]+=(board[i][j]-'0');

                        }

                        dpM[i][j]=mCnt%modulus;

                    }

                }

            }

        }

        return vector<int>{dpS[0][0],(int)(dpM[0][0]%modulus)};

    }

};

snow 07-05 10:33

3楼

设 dp_{i,j,0/1} ，为第 i 行， j 格的最大权值和及路径方案数

1. 最大权值和 dp_{i,j,0}

dp_{i,j,0} = \max \begin{cases}
dp_{i+1, j+1, 0} & \text{if } dp_{i+1, j+1, 0} \neq -1 \\
dp_{i+1, j, 0} & \text{if } dp_{i+1, j, 0} \neq -1 \\
dp_{i, j+1, 0} & \text{if } dp_{i, j+1, 0} \neq -1
\end{cases} + w_{i,j}

2. 路径方案数 dp_{i,j,1}

dp_{i,j,1} = \left( \sum \begin{cases}
dp_{i+1, j+1, 1} & \text{if } dp_{i+1, j+1, 0} + w_{i,j} = dp_{i,j,0} \\
dp_{i+1, j, 1} & \text{if } dp_{i+1, j, 0} + w_{i,j} = dp_{i,j,0} \\
dp_{i, j+1, 1} & \text{if } dp_{i, j+1, 0} + w_{i,j} = dp_{i,j,0}
\end{cases} \right) \pmod{10^9+7}

class Solution {

public:

    vector<int> pathsWithMaxScore(vector<string>& board) {

        int n = board.size(), m = board[0].size();

        vector dp(n, vector<array<int, 2>>(m, {-1, 0}));

        constexpr int MOD = 1E9 + 7;

        dp[n - 1][m - 1] = {0, 1};

        for (int i = n - 1; i >= 0; i--) {

            for (int j = m - 1; j >= 0; j--) {

                if (i == n - 1 && j == m - 1 || board[i][j] == 'X') continue;

                int w = (board[i][j] == 'E') ? 0 : (board[i][j] - '0');

                if (i + 1 <= n - 1 && j + 1 <= m - 1 && dp[i + 1][j + 1][0] != -1) {

                    if (dp[i + 1][j + 1][0] + w > dp[i][j][0]) {

                        dp[i][j][0] = dp[i + 1][j + 1][0] + w;

                        dp[i][j][1] = dp[i + 1][j + 1][1];

                    } else if (dp[i + 1][j + 1][0] + w == dp[i][j][0]) {

                        dp[i][j][1] = (1LL * dp[i][j][1] + dp[i + 1][j + 1][1]) % MOD;

                    }

                } 

                if (i + 1 <= n - 1 && dp[i + 1][j][0] != -1) {

                    if (dp[i + 1][j][0] + w > dp[i][j][0]) {

                        dp[i][j][0] = dp[i + 1][j][0] + w;

                        dp[i][j][1] = dp[i + 1][j][1];

                    } else if (dp[i + 1][j][0] + w == dp[i][j][0]) {

                        dp[i][j][1] = (1LL * dp[i][j][1] + dp[i + 1][j][1]) % MOD;

                    }

                }

                if (j + 1 <= m - 1 && dp[i][j + 1][0] != -1) {

                    if (dp[i][j + 1][0] + w > dp[i][j][0]) {

                        dp[i][j][0] = dp[i][j + 1][0] + w;

                        dp[i][j][1] = dp[i][j + 1][1];

                    } else if (dp[i][j + 1][0] + w == dp[i][j][0]) {

                        dp[i][j][1] = (1LL * dp[i][j][1] + dp[i][j + 1][1]) % MOD;

                    }

                }

            }

        }

        if (dp[0][0][0] == -1) {

            return {0, 0};

        }

        return {dp[0][0][0], dp[0][0][1]};

    }

};

CPython 07-05 10:49

4楼

199. 二叉树的右视图 - 力扣（LeetCode）

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, val=0, left=None, right=None):

#         self.val = val

#         self.left = left

#         self.right = right

class Solution:

    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:

        if not root:

            return []

        q = deque([root])

        ans = []

        while q:

            n = len(q)

            for i in range(n):

                node = q.popleft()

                if i == n - 1:

                    ans.append(node.val)

                if node.left:

                    q.append(node.left)

                if node.right:

                    q.append(node.right)

        return ans

Rebuilding 07-05 10:51

5楼

class Solution {

    public int[] pathsWithMaxScore(List<String> board) {

        int n = board.size();

        int[][] dpScore = new int[n][n];

        int[][] dpPaths = new int[n][n];

        // 1. 初始化

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < n; j++) {

                dpScore[i][j] = -1;

            }

        }

        dpScore[n - 1][n - 1] = 0;

        dpPaths[n - 1][n - 1] = 1;

        int mod = 1000000007;

        // 2. 倒序状态转移

        for (int i = n - 1; i >= 0; i--) {

            for (int j = n - 1; j >= 0; j--) {

                // 跳过起点

                if (i == n - 1 && j == n - 1) {

                    continue;

                }

                char c = board.get(i).charAt(j);

                // 遇到障碍物直接跳过

                if (c == 'X') {

                    continue;

                }

                int val = (c == 'E') ? 0 : (c - '0');

                int maxPrev = -1;

                int paths = 0;

                // 检查三个可能的来源方向：下方、右方、右下方

                int[][] dirs = { { i + 1, j }, { i, j + 1 }, { i + 1, j + 1 } };

                for (int[] dir : dirs) {

                    int r = dir[0];

                    int cDir = dir[1];

                    // 边界检查，且该来源方向必须是可达的（路径数 > 0）

                    if (r < n && cDir < n && dpPaths[r][cDir] > 0) {

                        if (dpScore[r][cDir] > maxPrev) {

                            maxPrev = dpScore[r][cDir];

                            paths = dpPaths[r][cDir];

                        } else if (dpScore[r][cDir] == maxPrev) {

                            paths = (paths + dpPaths[r][cDir]) % mod;

                        }

                    }

                }

                // 如果三个方向中至少有一个是可达的，更新当前位置的值

                if (maxPrev != -1) {

                    dpScore[i][j] = maxPrev + val;

                    dpPaths[i][j] = paths;

                }

            }

        }

        // 3. 返回结果：若终点可达，返回其得分与路径数；否则返回 [0, 0]

        if (dpPaths[0][0] == 0) {

            return new int[] { 0, 0 };

        }

        return new int[] { dpScore[0][0], dpPaths[0][0] };

    }

}

* 帖子来源Linux.do

附近帖子

飞读

魔法师

主题数
1

帖子数
1

注册排名
3

随机推荐