【动态规划】1301. 最大得分的路径数目

2024-02-12 05:44
文章标签 动态 规划 路径 最大 1301 数目 得分

本文主要是介绍【动态规划】1301. 最大得分的路径数目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者推荐

【动态规划】【前缀和】【C++算法】LCP 57. 打地鼠

本文涉及知识点

动态规划汇总

LeetCoce1301. 最大得分的路径数目

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

动态规划

动态规划的状态表示

dp1[r][c] 表示到达的最大分数，dp2[r][c] 表示方案数,0表示状态不存在。d

动态规划的转移方程

已知dp1[r][c] dp2[r][c]。如果dp1[r][c]<0，忽略。
{ 更新 r − 1 , c − 1 r > 0 且 c > 0 更新 r − 1 , c r > 0 更新 r , c − 1 c > 0 \begin{cases} 更新r-1,c-1 & r>0且c>0 \\ 更新r-1,c & r>0 \\ 更新r,c-1 & c > 0 \\ \end{cases} ⎩ ⎨ ⎧​更新r−1,c−1更新r−1,c更新r,c−1​r>0且c>0r>0c>0​

更新状态：
如果目标状态是障碍，忽略。
{ 忽略 新分数小于旧分数 d p 2 + = d p [ r ] [ c ] 新旧分数相等 更新 d p 1 , d p 2 = d p [ r ] [ c ] 其它 \begin{cases} 忽略 & 新分数小于旧分数 \\ dp2 += dp[r][c] & 新旧分数相等\\ 更新dp1,dp2 = dp[r][c] & 其它 \end{cases} ⎩ ⎨ ⎧​忽略dp2+=dp[r][c]更新dp1,dp2=dp[r][c]​新分数小于旧分数新旧分数相等其它​

动态规划的初始状态

起点格为dp1为0,dp2为1。其它格-1,0.

动态规划的填表顺序

从最后一行到第一行，从最后一列到第一列。

动态规格的返回值

dp1[0][0] 如果为-1，返回{0,0}。
否则返回{dp1[0][0],dp2[0][0]}

代码

核心代码

template<int MOD = 1000000007>
class C1097Int
{
public:C1097Int(long long llData = 0) :m_iData(llData% MOD){}C1097Int  operator+(const C1097Int& o)const{return C1097Int(((long long)m_iData + o.m_iData) % MOD);}C1097Int& operator+=(const C1097Int& o){m_iData = ((long long)m_iData + o.m_iData) % MOD;return *this;}C1097Int& operator-=(const C1097Int& o){m_iData = (m_iData + MOD - o.m_iData) % MOD;return *this;}C1097Int  operator-(const C1097Int& o){return C1097Int((m_iData + MOD - o.m_iData) % MOD);}C1097Int  operator*(const C1097Int& o)const{return((long long)m_iData * o.m_iData) % MOD;}C1097Int& operator*=(const C1097Int& o){m_iData = ((long long)m_iData * o.m_iData) % MOD;return *this;}bool operator<(const C1097Int& o)const{return m_iData < o.m_iData;}C1097Int pow(long long n)const{C1097Int iRet = 1, iCur = *this;while (n){if (n & 1){iRet *= iCur;}iCur *= iCur;n >>= 1;}return iRet;}C1097Int PowNegative1()const{return pow(MOD - 2);}int ToInt()const{return m_iData;}
private:int m_iData = 0;;
};class Solution {
public:vector<int> pathsWithMaxScore(vector<string>& board) {const int n = board.size();vector<vector<int>> dp1(n, vector<int>(n, -1));vector<vector<C1097Int<>>> dp2(n, vector<C1097Int<>>(n));dp1.back().back() = 0;dp2.back().back() = 1;for (int r = n - 1; r >= 0; r--){for (int c = n - 1; c >= 0; c--){auto Update = [&](int r1, int c1){if ((r1 < 0) || (c1 < 0)){return;}const char& ch = board[r1][c1];if ('X' == ch ){return ;}const int iNew = dp1[r][c] + (isdigit(ch) ? (ch - '0') : 0);if (iNew == dp1[r1][c1]){dp2[r1][c1] += dp2[r][c];}if (iNew > dp1[r1][c1]){dp1[r1][c1] = iNew;dp2[r1][c1] = dp2[r][c];}};if (dp1[r][c] < 0){continue;}Update(r - 1, c - 1);Update(r    , c - 1);Update(r - 1, c    );}}if (dp1[0][0] < 0){return { 0,0 };}return { dp1[0][0],dp2[0][0].ToInt() };}
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}}int main()
{	vector<string> board;{Solution sln;board = { "E23", "2X2", "12S" };auto res = sln.pathsWithMaxScore(board);Assert(vector<int>{7, 1}, res);}{Solution sln;board = { "E12", "1X1", "21S" };auto res = sln.pathsWithMaxScore(board);Assert(vector<int>{4,2}, res);}{Solution sln;board = { "E11", "XXX", "11S" };auto res = sln.pathsWithMaxScore(board);Assert(vector<int>{0, 0}, res);}
}

2023年2月

class C1097Int
{
public:
C1097Int(int iData = 0) :m_iData(iData)
{

 }C1097Int  operator+(const C1097Int& o)const{return C1097Int((m_iData + o.m_iData) % s_iMod);}C1097Int&  operator+=(const C1097Int& o){m_iData = (m_iData + o.m_iData) % s_iMod;return *this;}C1097Int  operator*(const C1097Int& o)const{return((long long)m_iData *o.m_iData) % s_iMod;}C1097Int&  operator*=(const C1097Int& o){m_iData =((long long)m_iData *o.m_iData) % s_iMod;return *this;}int ToInt()const{return m_iData;}

private:
int m_iData = 0;;
static const int s_iMod = 1000000007;
};

int operator+(int iData, const C1097Int& int1097)
{
int iRet = int1097.operator+(C1097Int(iData)).ToInt();
return iRet;
}

int& operator+=(int& iData, const C1097Int& int1097)
{
iData = int1097.operator+(C1097Int(iData)).ToInt();
return iData;
}

template
void MinSelf(T* seft, const T& other)
{
*seft = min(*seft, other);
}

template
void MaxSelf(T* seft, const T& other)
{
*seft = max(*seft, other);
}

int GetNotRepeateNum(int len, int iHasSel)
{
if (0 == len)
{
return 1;
}
if ((0 == iHasSel) && (1 == len))
{
return 10;
}
int iRet = 1;
if (iHasSel > 0)
{
for (int tmp = 10 - iHasSel; (tmp >= 2)&& len ; tmp–,len–)
{
iRet *= tmp;
}
}
else
{
iRet *= 9;
len–;
for (int tmp=9; (tmp>=2)&&len; len–,tmp–)
{
iRet *= tmp;
}
}
return iRet;
}

class Solution {
public:
vector pathsWithMaxScore(vector& board) {
m_r = board.size();
m_c = board[0].size();
m_vScource.assign(m_r, vector(m_c, -1));
m_vNum.assign(m_r, vector(m_c));
m_vScource[m_r - 1][m_c - 1] = 0;
m_vNum[m_r - 1][m_c - 1] = 1;
for (int r = m_r - 1; r >= 0; r–)
{
for (int c = m_c - 1; c >= 0; c–)
{
const char& ch = board[r][c];
if (‘X’ == ch)
{
continue;
}
int iCurSource = ((‘S’ == ch) || (‘E’ == ch)) ? 0 : ch - ‘0’;
//从右边来
Test(r, c + 1, r, c, iCurSource);
//从下边来
Test(r+1, c , r, c, iCurSource);
//从右下来
Test(r+1, c + 1, r, c, iCurSource);
}
}
if (-1 == m_vScource[0][0])
{
return {0, 0};
}
return{ m_vScource[0][0], m_vNum[0][0].ToInt() };
}
void Test(int iPreRow, int iPreCol, int r, int c, int iCurSource)
{
if (iPreRow >= m_r)
{
return;
}
if (iPreCol >= m_c)
{
return;
}
if (-1 == m_vScource[iPreRow][iPreCol])
{
return;
}
const int iNewSource = m_vScource[iPreRow][iPreCol] + iCurSource;
if (iNewSource < m_vScource[r][c])
{
return;
}
if (iNewSource == m_vScource[r][c])
{
m_vNum[r][c] += m_vNum[iPreRow][iPreCol];
return;
}
m_vScource[r][c] = iNewSource;
m_vNum[r][c] = m_vNum[iPreRow][iPreCol];
}
int m_r = 0, m_c = 0;
vector<vector> m_vScource;
vector<vector> m_vNum;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

这篇关于【动态规划】1301. 最大得分的路径数目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/701782。

相关文章

hdu1496（用hash思想统计数目）

hdu1496（用hash思想统计数目）

作为一个刚学hash的孩子，感觉这道题目很不错，灵活的运用的数组的下标。 解题步骤：如果用常规方法解，那么时间复杂度为O（n^4）,肯定会超时，然后参考了网上的解题方法，将等式分成两个部分，a*x1^2+b*x2^2和c*x3^2+d*x4^2， 各自作为数组的下标，如果两部分相加为0，则满足等式； 代码如下： #include<iostream>#include<algorithm
阅读更多...
第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
hdu2544（单源最短路径）

hdu2544（单源最短路径）

模板题： //题意：求1到n的最短路径，模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i
阅读更多...
动态规划---打家劫舍

动态规划---打家劫舍

题目： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路： 动态规划五部曲： 1.确定dp数组及含义 dp数组是一维数组，dp[i]代表
阅读更多...
poj 1734 （floyd求最小环并打印路径）

poj 1734 （floyd求最小环并打印路径）

题意： 求图中的一个最小环，并打印路径。 解析： ans 保存最小环长度。 一直wa，最后终于找到原因，inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用，但是还是有局限性。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl
阅读更多...
软考系统规划与管理师考试证书含金量高吗？

软考系统规划与管理师考试证书含金量高吗？

2024年软考系统规划与管理师考试报名时间节点： 报名时间：2024年上半年软考将于3月中旬陆续开始报名 考试时间：上半年5月25日到28日，下半年11月9日到12日 分数线：所有科目成绩均须达到45分以上（包括45分）方可通过考试 成绩查询：可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间：预计在11月左右 证书领取时间：一般在考试成绩公布后3~4个月，各地领取时间有所不同
阅读更多...
poj 3723 kruscal，反边取最大生成树。

poj 3723 kruscal，反边取最大生成树。

题意： 需要征募女兵N人，男兵M人。 每征募一个人需要花费10000美元，但是如果已经招募的人中有一些关系亲密的人，那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度，征募某个人的费用是10000 - （已经征募的人中和自己的亲密度的最大值）。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析： 先设想无向图，在征募某个人a时，如果使用了a和b之间的关系
阅读更多...
poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976： 题意： 在n场考试中，每场考试共有b题，答对的题目有a题。 允许去掉k场考试，求能达到的最高正确率是多少。 解析： 假设已知准确率为x，则每场考试对于准确率的贡献值为： a - b * x，将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码： #include <iostream>#include <cstdio>#incl
阅读更多...
poj 3258 二分最小值最大

poj 3258 二分最小值最大

题意： 有一些石头排成一条线，第一个和最后一个不能去掉。 其余的共可以去掉m块，要使去掉后石头间距的最小值最大。 解析： 二分石头，最小值最大。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c
阅读更多...
poj 2175 最小费用最大流TLE

poj 2175 最小费用最大流TLE

题意： 一条街上有n个大楼，坐标为xi，yi，bi个人在里面工作。 然后防空洞的坐标为pj，qj，可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs（xi - pi） + （yi - qi） + 1。 现在设计了一个避难计划，指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行，所有人避难所用的时间总和是不是最小的。 若是，输出“OPETIMAL",若
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2