算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域优质创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果 题目要求题目描述 核心逻辑拆解 实现代码 关键原理说明 正反 DP 模型等价性 遍历顺序的硬性约束 负无穷初始化的作用取模时机 运行效率 时间复杂度空间复杂度 共勉 题目链接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 求解思路实现代码运行结果 题目要求题目描述棋盘为 n×n 矩阵左上角字符 E 是终点右下角字符 S 是起点其余位置为数字 0~9 或障碍 X。行走规则从起点 S 前往终点 E每一步仅能向上、向左、向左上移动不能走入障碍 X。计分规则起点 S、终点 E 不计入分数路径经过的数字格子累加为总得分。输出两个值能从 S 走到 E 的最大路径得分得到该最大得分的路径总数结果对 (10^97) 取模若不存在任何合法路径直接返回 [0,0]。 核心逻辑拆解思路选择正向 DP以 E 为起点推导常规思路是从起点 S 倒推至终点 E本次采用反向建模以终点 E 作为 DP 起点正向遍历推导至 S。状态定义(dpMax[i][j])从 E (0,0) 走到坐标((i,j))能获得的最大分数(dpCnt[i][j])从 E 走到((i,j))且取得(dpMax[i][j])分数的路径条数。行走方向反转原题正向S → E走 上、左、左上DP 反向E → S走 下、右、右下因此每个格子((i,j))的分数只能由上方((i-1,j))、左方((i,j-1))、左上方((i-1,j-1))三个位置转移而来。初始化规则DP 起点为 E (0,0)E 不计分到达自身仅 1 种方式(dpMax[0][0]0dpCnt[0][0]1)其余格子初始值为负无穷代表初始不可达。分数累加规则仅数字格子加分E、S 不参与计分遇到障碍 X 直接跳过不参与状态转移。状态转移流程① 找出三个前驱格子中的最大分数prevMax② 若所有前驱都不可达当前格子保持不可达③ 当前格子最大分数 前驱最大分数 当前格子分值④ 累加所有分数等于prevMax的前驱路径数对 MOD 取模。结果取值DP 遍历完成后右下角 S((n-1,n-1))存储的值即为答案(dpMax[n-1][n-1]) 最大得分(dpCnt[n-1][n-1]) 对应路径数量若为负无穷代表无通路返回[0,0]。 实现代码classSolution{privatestaticfinalintMOD1000000007;publicint[]pathsWithMaxScore(ListStringboard){intnboard.size();// dpMax[i][j]从E(0,0)走到(i,j)的最大分数long[][]dpMaxnewlong[n][n];// dpCnt[i][j]对应最大分数的路径数long[][]dpCntnewlong[n][n];// 初始化为极小值代表不可达for(inti0;in;i){for(intj0;jn;j){dpMax[i][j]Long.MIN_VALUE;}}// DP起点终点E(0,0)初始化dpMax[0][0]0;dpCnt[0][0]1;// 正序遍历从上到下、从左到右for(inti0;in;i){for(intj0;jn;j){charcboard.get(i).charAt(j);// 障碍无法通行跳过if(cX)continue;// E点已完成初始化无需重复计算if(i0j0)continue;// 计分E、S不计分数字格子累加数值longadd0;if(c!S){addc-0;}// 三个前驱上、左、左上longprevMaxLong.MIN_VALUE;if(i-10)prevMaxMath.max(prevMax,dpMax[i-1][j]);if(j-10)prevMaxMath.max(prevMax,dpMax[i][j-1]);if(i-10j-10)prevMaxMath.max(prevMax,dpMax[i-1][j-1]);// 无有效前驱当前格子不可达if(prevMaxLong.MIN_VALUE)continue;// 更新当前格子最大分数dpMax[i][j]prevMaxadd;// 累加所有等于前驱最大值的路径数longtotal0;if(i-10dpMax[i-1][j]prevMax){total(totaldpCnt[i-1][j])%MOD;}if(j-10dpMax[i][j-1]prevMax){total(totaldpCnt[i][j-1])%MOD;}if(i-10j-10dpMax[i-1][j-1]prevMax){total(totaldpCnt[i-1][j-1])%MOD;}dpCnt[i][j]total;}}// 最终结果存在起点S(n-1,n-1)longmaxScoredpMax[n-1][n-1];longcountdpCnt[n-1][n-1];// 无合法路径返回[0,0]if(maxScoreLong.MIN_VALUE){returnnewint[]{0,0};}returnnewint[]{(int)maxScore,(int)count};}} 关键原理说明 正反 DP 模型等价性逆序 DPS 初始化倒序遍历结果取 E正向 DP本文E 初始化正序遍历结果取 S两条路径模型只是行进方向相反路径总得分、路径总数完全一致数学等价。 遍历顺序的硬性约束本方案状态((i,j))依赖坐标更小的(i-1、j-1)格子因此必须从上到下、从左到右正序遍历保证计算当前格子时所有前驱格子已经完成计算。 负无穷初始化的作用区分 “不可达格子” 与 “分数为 0 的格子”避免障碍、断路位置错误参与分数转移。取模时机路径数累加时实时对 (10^97) 取模防止 long 数组溢出符合题目输出要求。 运行效率 时间复杂度时间复杂度(O(n^2))棋盘总格子数 (n×n)每个格子仅执行一次转移逻辑仅三次前驱判断、路径累加无重复计算n 最大 100 时仅 10000 次循环运算量极低。空间复杂度空间复杂度(O(n^2))使用两个二维 long 数组存储最大分数与路径计数若追求极致空间可滚动数组优化常规场景二维数组可读性更高。 共勉最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉