原文链接: https://leetcode-cn.com/problems/number-of-paths-with-max-score

英文原文

You are given a square board of characters. You can move on the board starting at the bottom right square marked with the character 'S'.

You need to reach the top left square marked with the character 'E'. The rest of the squares are labeled either with a numeric character 1, 2, ..., 9 or with an obstacle 'X'. In one move you can go up, left or up-left (diagonally) only if there is no obstacle there.

Return a list of two integers: the first integer is the maximum sum of numeric characters you can collect, and the second is the number of such paths that you can take to get that maximum sum, taken modulo 10^9 + 7.

In case there is no path, return [0, 0].

 

Example 1:

Input: board = ["E23","2X2","12S"]
Output: [7,1]

Example 2:

Input: board = ["E12","1X1","21S"]
Output: [4,2]

Example 3:

Input: board = ["E11","XXX","11S"]
Output: [0,0]

 

Constraints:

• 2 <= board.length == board[i].length <= 100

中文题目

给你一个正方形字符数组 board ，你从数组最右下方的字符 'S' 出发。

你的目标是到达数组最左上角的字符 'E' ，数组剩余的部分为数字字符 1, 2, ..., 9 或者障碍 'X'。在每一步移动中，你可以向上、向左或者左上方移动，可以移动的前提是到达的格子没有障碍。

一条路径的 「得分」 定义为：路径上所有数字的和。

请你返回一个列表，包含两个整数：第一个整数是 「得分」 的最大值，第二个整数是得到最大得分的方案数，请把结果对 10^9 + 7 取余。

如果没有任何路径可以到达终点，请返回 [0, 0] 。

 

示例 1：

输入：board = ["E23","2X2","12S"]
输出：[7,1]

示例 2：

输入：board = ["E12","1X1","21S"]
输出：[4,2]

示例 3：

输入：board = ["E11","XXX","11S"]
输出：[0,0]

 

提示：

• 2 <= board.length == board[i].length <= 100

通过代码

高赞题解

前言

今天是我们讲解动态规划专题中的 路径问题 的第十天。

也是我们本专题的最后一章。

我在文章结尾处列举了本专题所有路径问题的相关链接，方便你进行回顾。

---

动态规划

本题是一道综合类的题目，不仅仅要求我们求「最大得分」，还需要统计得到最大得分的「方案数」。

显然，两个问题都属于无后效性问题，可以使用 DP 进行求解。

按理说，我们需要使用「二维数组」来存储我们的动规值。

但是维度的增加会让我们的「出错概率」和「Debug 难度」增加。

因此，通常我们会有能合并维度就合并维度的原则。

这里我们将 $(x,y)$ 使用一个下标 $idx$ 进行替代。

前面两节我们都在使用 动态规划通用解法 中的技巧解法，那么本节就回顾一下最开始学习的经验解法吧。

• 最大得分问题

结合「最后一步」猜测状态定义：$f(idx)$ 为从「起点」到下标为 $idx$ 的最大得分。

那么 $f(0)$ 就是最终答案。

结合题意，对于某个位置可以由「下方」、「右方」和「右下方」三个位置转移而来。

因此我们可以得出状态转移方程为：

$$f[(x,y)]=max(f[(x+1,y)],f[(x,y+1)],f[(x+1,y+1)])+board[(x,y)]$$

当然，只有合法范围内的格子才会参与转移，同时存在「障碍物」的格子的动规值为 INF（负数）。

• 最大得分方案数问题

同理，使用一个 g[] 数组来存储我们的方案数。

由于某个位置可以由「下方」、「右方」和「右下方」三个位置转移而来。

同时 f[(x,y)] 是由三个位置的最大值转移过来，那么相应的 g[(x,y)] 应该取到最大得分的转移位置的方案数。

需要注意，最大值不一定是由一个位置得出。

如果有多个位置同时能取到最大得分，那么方案数应该是多个位置的方案数之和。

举个🌰，如果可到达 $(x,y)$ 的三个位置（ $(x+1,y)$，$(x,y+1)$，$(x+1,y+1)$ ）的最大得分为 3，4，5，到达三个位置的方案数为 1，2，2。

那么可得：

$$ \left{
\begin{aligned}
f[(x,y)]&= 5 + board[(x,y)]\
g[(x.y)]&= 2
\end{aligned}
\right.$$

但如果三个位置的最大得分为 3，5，5，到达三个位置的方案数为 1，2，2 的话。

由于同时取得最大值的位置有两个，那么方案数也应该是两个位置方案数之和。

即有：

$$ \left{
\begin{aligned}
f[(x,y)]&= 5 + board[(x,y)]\
g[(x.y)]&= 2 + 2
\end{aligned}
\right.$$

以上就是我们两个 DP 问题的主要逻辑分析。

还有一些其他的编码细节，我也已经写到了注释当中。

代码：

class Solution {
    int INF = Integer.MIN_VALUE;
    int mod = (int)1e9+7;
    int n;
    public int[] pathsWithMaxScore(List<String> board) {
        n = board.size();

        // 将 board 转存成二维数组
        char[][] cs = new char[n][n];
        for (int i = 0; i < n; i++) {
            cs[i] = board.get(i).toCharArray();
        }

        // f(i) 代表从右下角到位置 i 的最大得分
        int[] f = new int[n * n]; 
        // f(i) 代表从右下角到位置 i 并取到最大得分的方案数量
        int[] g = new int[n * n]; 
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int idx = getIdx(i, j);

                // 一个初始化的状态，如果是在最后一格（起点）：
                // g[idx] = 1 : 代表到达起点的路径只有一条，这样我们就有了一个「有效值」可以滚动下去
                // f[idx] = 0 : 代表在起点得分为 0
                if (i == n - 1 && j == n - 1) {
                    g[idx] = 1;
                    continue;
                }

                // 如果该位置是「障碍点」，那么对应状态为：
                // g[idx] = 0   : 「障碍点」不可访问，路径为 0
                // f[idx] = INF : 「障碍点」不可访问，得分为无效值
                if (cs[i][j] == 'X') {
                    f[idx] = INF;
                    continue;
                }

                // 如果是第一个格子（终点），这时候位置得分为 0
                int val = (i == 0 && j == 0) ? 0 : cs[i][j] - '0';

                // u 代表当前位置的「最大得分」；t 代表取得最大得分的「方案数」
                int u = INF, t = 0;

                // 如果「下方格子」合法，尝试从「下方格子」进行转移
                if (i + 1 < n) {    
                    int cur = f[getIdx(i + 1, j)] + val;
                    int cnt =  g[getIdx(i + 1, j)];
                    int[] res = update(cur, cnt, u, t);
                    u = res[0]; t = res[1];
                }

                // 如果「右边格子」合法，尝试从「右边格子」进行转移
                if (j + 1 < n) {
                    int cur = f[getIdx(i, j + 1)] + val;
                    int cnt = g[getIdx(i, j + 1)];
                    int[] res = update(cur, cnt, u, t);
                    u = res[0]; t = res[1];
                }

                // 如果「右下角格子」合法，尝试从「右下角格子」进行转移
                if (i + 1 < n && j + 1 < n) {
                    int cur = f[getIdx(i + 1, j + 1)] + val;
                    int cnt = g[getIdx(i + 1, j + 1)];
                    int[] res = update(cur, cnt, u, t);
                    u = res[0]; t = res[1];
                }

                // 更新 dp 值
                f[idx] = u < 0 ? INF : u;
                g[idx] = t;
            }
        }

        // 构造答案
        int[] ans = new int[2];
        // 如果终点不可达（动规值为 INF）时，写入 0
        ans[0] = f[getIdx(0, 0)] == INF ? 0 : f[getIdx(0, 0)];
        // 如果终点不可达（动规值为 INF）时，写入 0
        ans[1] = f[getIdx(0, 0)] == INF ? 0 : g[getIdx(0, 0)];
        return ans;
    }

    // 更新 dp 值
    int[] update(int cur, int cnt, int u, int t) {
        // 起始答案为 [u, t] : u 为「最大得分」，t 为最大得分的「方案数」
        int[] ans = new int[]{u, t};

        // 如果当前值大于 u，更新「最大得分」和「方案数」
        if (cur > u) {
            ans[0] = cur;
            ans[1] = cnt;

        // 如果当前值等于 u，增加「方案数」
        } else if (cur == u && cur != INF) {
            ans[1] += cnt;
        }
        
        ans[1] %= mod;
        return ans;
    }
    
    // 二维坐标 (x,y) 与 idx 的相互转换
    int getIdx(int x, int y) {
        return x * n + y;
    }
    int[] parseIdx(int idx) {
        return new int[]{idx / n, idx % n};
    }
}

• 时间复杂度：共有 $n^2$ 个状态需要被转移，复杂度为 $O(n^2)$
• 空间复杂度：$O(n^2)$

---

总结

在本讲，我们解决了一道动态规划的综合题。

我们通过最开始学习的经验解法来进行求解。

事实上，对于两种 动态规划通用解法 的选择，我们应该遵循以下原则进行选择：

1. 对于一些我们熟悉的题目，或是维度不多的题目，应当优先选择经验解法。
2. 对于一些我们没接触过的题目，应当使用技巧解法。

关于「经验解法」有以下注意点：

在 经验解法 中，猜测 状态定义 时应当结合最后一步进行猜测，当有了一个正确的「状态定义」之后，通常「状态方程」总是呼之欲出的。

因此如果「状态方程」很难推导出来，或者推导出来的「转移方程」无法满足转移要求（【不重不漏】或者【不漏】）。很大程度上是我们的「状态定义」猜错了，需要重新猜测。

关于「技巧解法」有以下注意点：

通常我们需要有一个「记忆化搜索」的解决方案，然后在此解决方案的基础上转成「动态规划」。

事实上，「记忆化搜索」本身与「动态规划」并无效率区别，因此如果我们真的有一个「记忆化搜索」方案的话，其实并没有“翻译”成「动态规划」的必要。

但「技巧解法」强调的是，我们只需要有一个「记忆化搜索」的 DFS 函数签名即可，而不用真的去实现一个「记忆化搜索」。

所谓的“翻译”过程也是帮助我们从 DFS 函数签名中得到一个可靠的「状态定义」而已，当有了「状态定义」之后，我们仍然要和「经验解法」一样，去分析「状态方程」。

---

路径问题（目录）

62.不同路径（中等）：路径问题第一讲

63.不同路径 II（中等）：路径问题第二讲

64.最小路径和（中等）：路径问题第三讲

120.三角形最小路径和（中等）：路径问题第四讲

931.下降路径最小和（中等）：路径问题第五讲

1289.下降路径最小和 II（困难）：路径问题第六讲

1575.统计所有可行路径（困难）：路径问题第七讲（记忆化搜索）

1575.统计所有可行路径（困难）：路径问题第八讲（动态规划）

576.出界的路径数（中等）：路径问题第九讲

1301.最大得分的路径数目（困难）：路径问题第十讲

欢迎补充 ~

---

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

如有不理解的地方，欢迎你在评论区给我留言，我都会逐一回复 ~

也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解

统计信息

通过次数	提交次数	AC比率
3544	9797	36.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言