iis新建网站无法浏览,域名解析 别人网站,网站建设公司固定ip,国内外贸免费网站建设动态规划解题步骤#xff1a;
1.确定状态表示#xff1a;dp[i]是什么
2.确定状态转移方程#xff1a;dp[i]等于什么
3.初始化#xff1a;确保状态转移方程不越界
4.确定填表顺序#xff1a;根据状态转移方程即可确定填表顺序
5.确定返回值
题目链接#xff1a;174.…动态规划解题步骤
1.确定状态表示dp[i]是什么
2.确定状态转移方程dp[i]等于什么
3.初始化确保状态转移方程不越界
4.确定填表顺序根据状态转移方程即可确定填表顺序
5.确定返回值
题目链接174. 地下城游戏 - 力扣LeetCode 题解
本题使用从起点开始到达dp[i][j]位置的方法行不通因为dp[i][j]不仅被前面的位置影响还会被后面位置影响
所以本题使用从dp[i][j]位置开始到达终点的方法
1.状态表示dp[i][j]表示从dungeon[i][j]位置出发到达终点所需最低初始健康点数
2.状态转移方程dp[i][j]min(dp[i1][j],dp[i][j1])-dungeon[i][j]; if(dp[i][j]0) dp[i][j]1
3.初始化在右下角多开一行一列初始化和填表合并多开位置需要填值[m][n-1]和[m-1][n]位置填1其余位置为正无穷
4.填表顺序从右下角往左上角填写
5.返回值dp[0][0]
class Solution {
public:int calculateMinimumHP(vectorvectorint dungeon) {//状态表示//dp[i][j]表示从dungeon[i][j]位置出发到达终点所需最低初始健康点数//状态转移方程//dp[i][j]min(dp[i1][j]-dungeon[i][j],dp[i][j1]-dungeon[i][j])//if(dp[i][j]0) dp[i][j]1//创建dp表size_t mdungeon.size();size_t ndungeon[0].size();vectorvectorint dp(m1,vectorint(n1,INT_MAX));//多开一行一列但是右下角//初始化dp[m][n-1]dp[m-1][n]1;//填表从右下角到左上角for(int im-1;i0;--i){for(int jn-1;j0;--j){dp[i][j]min(dp[i1][j],dp[i][j1])-dungeon[i][j];if(dp[i][j]0) dp[i][j]1;//最低健康值不可能为负数或0最低为1}}return dp[0][0];}
};
这是使用从起点开始到达dp[i][j]位置的方法此代码不行
class Solution {
public:int calculateMinimumHP(vectorvectorint dungeon) {//dp[i][j]表示到达dungeon[i][j]所需的最低初始健康点数//if(dungeon[i][j]0)//dp[i][j]min(dp[i-1][j]-dungeon[i][j],dp[i][j-1]-dungeon[i][j])//创建dp表size_t mdungeon.size();size_t ndungeon[0].size();vectorvectorint dp(m1,vectorint(n1,INT_MAX));//多开一行一列dp[0][1]dp[1][0]1;//填表for(int i1;im1;i){for(int j1;jn1;j){if(dungeon[i-1][j-1]0)dp[i][j]min(dp[i-1][j]-dungeon[i-1][j-1],dp[i][j-1]-dungeon[i-1][j-1]);elsedp[i][j]min(dp[i-1][j],dp[i][j-1]);}}return dp[m][n];}
};
