网站开发费用如何记账,网站推广怎么推广,网络培训的好处,hp网站1. 地下城游戏 题目链接#xff1a; 174. 地下城游戏 - 力扣#xff08;LeetCode#xff09;https://leetcode.cn/problems/dungeon-game/description/ 2. 算法原理 状态表示#xff1a;以莫一个位置位置为结尾或者以莫一个位置为起点 dp[i#xff0c;j]表示#xff1a…1. 地下城游戏 题目链接 174. 地下城游戏 - 力扣LeetCodehttps://leetcode.cn/problems/dungeon-game/description/ 2. 算法原理 状态表示以莫一个位置位置为结尾或者以莫一个位置为起点 dp[ij]表示到达[ij]位置的时候骑士所需要的最低初始健康点数X这个状态表示是错误的因为如果是以莫一个位置为结尾来推导的话我们会发现我们正向推导的时候是不断的修改我们之前的状态无法得到一个准确的状态 所以本题应该以莫一个位置为起点来开始推断从[ij]位置出发到达终点dp[ij]里面存储的值就是所需的最低初始健康点数 2. 状态转移方程 根据最近的一步来划分问题 到达dp[i][j]有两种情况 1. 往右边走dp[ij1] - d[i][j] 2. 往下走dp[i1j] - d[i][j] 本题的状态转移方程是dp[i][j] min(dp[ij1] ,dp[i1j]) - d[i][j] 因为最低健康点数还有可能为负数那么我们还需要对它进行一次比对 dp[i][j] max(1,dp[i][j] ) 如果为负数则返回1否则不变 3. 初始化 把dp表填满不越界让后面的填表可以顺利进行 本题状态依赖的是下面和右边的状态所以会越界的位置是下面的一行和右边的一列那么我们可以在下面的一行和右边的一列再额外的加上一行和一列的虚拟节点 因为是在下面的一行和右边的一列加上了虚拟节点所以不用考虑下标的映射关系只需要保证后面的填表是正确的 当解救完公主之后走到下面或者右边的时候最少要剩下1滴健康点数其余虚拟节点的值是取最小的值为了防止影响到最终结果所以我们将其初始化为正无穷大 4. 填表顺序 本题的填表顺序是从下往上填写每一行每一行的值是从右往左 5. 返回值 题目要求 状态表示 本题的返回值是dp[0][0] 3.代码 动态规划的固定四步骤1. 创建一个dp表 2. 在填表之前初始化 3. 填表填表方法状态转移方程 4. 确定返回值 class Solution {
public:int calculateMinimumHP(vectorvectorint d) {int md.size(),nd[0].size();//创建dp表随便将虚拟节点全部初始化为正无穷大vectorvectorintdp(m1,vectorint(n1,INT_MAX));//再将dp[m][n-1]和dp[m-1][n]初始化为1dp[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])-d[i][j];dp[i][j]max(1,dp[i][j]);}return dp[0][0];}
}; 感谢观看~
