本文主要是介绍【动态规划】【hard】力扣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
动态规划
using PII = pair<int, int>;class Solution {
private:static constexpr int mod = (int)1e9 + 7;public:void update(vector<vector<PII>>& dp, int n, int x, int y, int u, int v){if(u >= n || v >= n || dp[u][v].first == -1){return;}if(dp[u][v].first > dp[x][y].first){dp[x][y] = dp[u][v];}else if(dp[u][v].first == dp[x][y].first){dp[x][y].second += dp[u][v].second;if(dp[x][y].second >= mod){dp[x][y].second -= mod;}}}vector<int> pathsWithMaxScore(vector<string>& board) {int n = board.size();vector<vector<PII>> dp(n, vector<PII>(n, {-1, 0}));dp[n-1][n-1] = {0, 1};for(int i = n - 1; i >= 0; i--){for(int j = n - 1; j >= 0; j--){if(!(i== n - 1 && j == n - 1) && board[i][j] != 'X'){update(dp, n, i, j, i+1, j);update(dp, n, i, j, i, j+1);update(dp, n, i, j, i+1, j+1);if(dp[i][j].first != -1){dp[i][j].first += (board[i][j] == 'E' ? 0 : board[i][j] - '0');}}}}return dp[0][0].first == -1 ? vector<int>{0,0} : vector<int>{dp[0][0].first, dp[0][0].second};}
};
这题由于要维护两个数组，而且要处理很多情况，所以处理过程较为复杂。先看主函数中，我们从右下角向左，向上来遍历所有网格。当处理一个网格的时候（当网格不在边缘时），他的最大得分和三个格子有关分别是下，右，右下。于是我们定义一个函数update用来减少代码量。
当处理一个网格的时候，如果他下或者右或者右下三个格子如果在网格外，那么就不考虑他，直接return。如果比较的格子最大得分大小比他大，那么就更新当前网格，如果得分等于比较的格子的话，那么就将路径数量+1，假设如果数量加一后，遇到另一个比较的格子比他大，那么又会更新成那个格子的dp（无论是得分还是路径数量）。
更新完了后，就要加上自身的得分，首先要判断是不是终点E，如果是的话，就加上0，不然的话就加上自身得分，由于是字符串，所以要减去’0’，才能得到整型。
最后返回终点E的dp，如果得分是-1，说明没有路径可以到达，返回{0,0}，否则就返回他的最大得分和路径和。
这篇关于【动态规划】【hard】力扣1301. 最大得分的路径数目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
