【LeetCode: 1301. 最大得分的路径数目 + DP】

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域优质创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚩 题目链接

• 1301. 最大得分的路径数目

⛲ 题目描述

给你一个正方形字符数组 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

🌟 求解思路&实现代码&运行结果

🥦 题目要求

🎯题目描述

1. 棋盘为 n×n 矩阵，左上角字符 E 是终点，右下角字符 S 是起点；其余位置为数字 0~9 或障碍 X。
2. 行走规则：从起点 S 前往终点 E，每一步仅能向上、向左、向左上移动，不能走入障碍 X。
3. 计分规则：起点 S、终点 E 不计入分数，路径经过的数字格子累加为总得分。
4. 输出两个值：

• 能从 S 走到 E 的最大路径得分；
• 得到该最大得分的路径总数，结果对 (10^9+7) 取模；

5. 若不存在任何合法路径，直接返回 [0,0]。

🥦 核心逻辑拆解

思路选择：正向 DP，以 E 为起点推导常规思路是从起点 S 倒推至终点 E，本次采用反向建模：以终点 E 作为 DP 起点，正向遍历推导至 S。

1. 状态定义
   (dpMax[i][j])：从 E (0,0) 走到坐标((i,j))能获得的最大分数；
   (dpCnt[i][j])：从 E 走到((i,j))且取得(dpMax[i][j])分数的路径条数。

2. 行走方向反转
   原题正向：S → E，走 上、左、左上；
   DP 反向：E → S，走 下、右、右下；
   因此每个格子((i,j))的分数只能由上方((i-1,j))、左方((i,j-1))、左上方((i-1,j-1))三个位置转移而来。

3. 初始化规则
   DP 起点为 E (0,0)，E 不计分，到达自身仅 1 种方式：
   (dpMax[0][0]=0，dpCnt[0][0]=1)；
   其余格子初始值为负无穷，代表初始不可达。

4. 分数累加规则
   仅数字格子加分，E、S 不参与计分；遇到障碍 X 直接跳过，不参与状态转移。
   状态转移流程
   ① 找出三个前驱格子中的最大分数prevMax；
   ② 若所有前驱都不可达，当前格子保持不可达；
   ③ 当前格子最大分数 = 前驱最大分数 + 当前格子分值；
   ④ 累加所有分数等于prevMax的前驱路径数，对 MOD 取模。

5. 结果取值
   DP 遍历完成后，右下角 S((n-1,n-1))存储的值即为答案：
   (dpMax[n-1][n-1]) 最大得分，(dpCnt[n-1][n-1]) 对应路径数量；若为负无穷代表无通路，返回[0,0]。

🥦 实现代码

classSolution{privatestaticfinalintMOD=1000000007;publicint[]pathsWithMaxScore(List<String>board){intn=board.size();// dpMax[i][j]：从E(0,0)走到(i,j)的最大分数long[][]dpMax=newlong[n][n];// dpCnt[i][j]：对应最大分数的路径数long[][]dpCnt=newlong[n][n];// 初始化为极小值，代表不可达for(inti=0;i<n;i++){for(intj=0;j<n;j++){dpMax[i][j]=Long.MIN_VALUE;}}// DP起点：终点E(0,0)初始化dpMax[0][0]=0;dpCnt[0][0]=1;// 正序遍历：从上到下、从左到右for(inti=0;i<n;i++){for(intj=0;j<n;j++){charc=board.get(i).charAt(j);// 障碍无法通行，跳过if(c=='X')continue;// E点已完成初始化，无需重复计算if(i==0&&j==0)continue;// 计分：E、S不计分，数字格子累加数值longadd=0;if(c!='S'){add=c-'0';}// 三个前驱：上、左、左上longprevMax=Long.MIN_VALUE;if(i-1>=0)prevMax=Math.max(prevMax,dpMax[i-1][j]);if(j-1>=0)prevMax=Math.max(prevMax,dpMax[i][j-1]);if(i-1>=0&&j-1>=0)prevMax=Math.max(prevMax,dpMax[i-1][j-1]);// 无有效前驱，当前格子不可达if(prevMax==Long.MIN_VALUE)continue;// 更新当前格子最大分数dpMax[i][j]=prevMax+add;// 累加所有等于前驱最大值的路径数longtotal=0;if(i-1>=0&&dpMax[i-1][j]==prevMax){total=(total+dpCnt[i-1][j])%MOD;}if(j-1>=0&&dpMax[i][j-1]==prevMax){total=(total+dpCnt[i][j-1])%MOD;}if(i-1>=0&&j-1>=0&&dpMax[i-1][j-1]==prevMax){total=(total+dpCnt[i-1][j-1])%MOD;}dpCnt[i][j]=total;}}// 最终结果存在起点S(n-1,n-1)longmaxScore=dpMax[n-1][n-1];longcount=dpCnt[n-1][n-1];// 无合法路径返回[0,0]if(maxScore==Long.MIN_VALUE){returnnewint[]{0,0};}returnnewint[]{(int)maxScore,(int)count};}}

🥦 关键原理说明

🎯 正反 DP 模型等价性

逆序 DP：S 初始化，倒序遍历，结果取 E；
正向 DP（本文）：E 初始化，正序遍历，结果取 S；
两条路径模型只是行进方向相反，路径总得分、路径总数完全一致，数学等价。

🎯 遍历顺序的硬性约束

本方案状态((i,j))依赖坐标更小的(i-1、j-1)格子，因此必须从上到下、从左到右正序遍历，保证计算当前格子时，所有前驱格子已经完成计算。

🎯 负无穷初始化的作用

区分 “不可达格子” 与 “分数为 0 的格子”，避免障碍、断路位置错误参与分数转移。

🎯取模时机

路径数累加时实时对 (10^9+7) 取模，防止 long 数组溢出，符合题目输出要求。

🥦 运行效率

🎯 时间复杂度

时间复杂度：(O(n^2))
棋盘总格子数 (n×n)，每个格子仅执行一次转移逻辑，仅三次前驱判断、路径累加，无重复计算；n 最大 100 时仅 10000 次循环，运算量极低。

🎯空间复杂度

空间复杂度：(O(n^2))
使用两个二维 long 数组存储最大分数与路径计数；若追求极致空间可滚动数组优化，常规场景二维数组可读性更高。

💬 共勉