百度做网站多少钱能做,wordpress搭建系统,南京宣传片拍摄制作公司,做一个网站的完整教程个人主页#xff1a;元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归算法题 http://t.csdnimg.cn/yUl2I
【C】
http://t.csdnimg.cn/6AbpV
数据结构与算法 http://t.csdnimg.cn/hKh2l 前言#xff1a;这个专栏主要讲述动…个人主页元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归算法题 http://t.csdnimg.cn/yUl2I
【C】
http://t.csdnimg.cn/6AbpV
数据结构与算法 http://t.csdnimg.cn/hKh2l 前言这个专栏主要讲述动态规划算法所以下面题目主要也是这些算法做的
我讲述题目会把讲解部分分为3个部分 1、题目解析
2、算法原理思路讲解
3、代码实现 地下城游戏
题目链接地下城游戏
题目
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下他会立即死亡。
有些房间由恶魔守卫因此骑士在进入这些房间时会失去健康点数若房间里的值为负整数则表示骑士将损失健康点数其他房间要么是空的房间里的值为 0要么包含增加骑士健康点数的魔法球若房间里的值为正整数则表示骑士将增加健康点数。
为了尽快解救公主骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意任何房间都可能对骑士的健康点数造成威胁也可能增加骑士的健康点数包括骑士进入的左上角房间以及公主被监禁的右下角房间。 示例 1 输入dungeon [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出7
解释如果骑士遵循最佳路径右 - 右 - 下 - 下 则骑士的初始健康点数至少为 7 。
示例 2
输入dungeon [[0]]
输出1提示
m dungeon.lengthn dungeon[i].length1 m, n 200-1000 dungeon[i][j] 1000 解法
算法原理讲解
我们这题使用动态规划我们做这类题目可以分为以下五个步骤
状态显示状态转移方程初始化防止填表时不越界填表顺序返回值
状态显示
这道题如果我们和以前的题目一样定义成从起点开始到达 [i, j] 位置的时候所需的最低初始健康点数。 那么我们分析状态转移的时候会有⼀个问题那就是我们当前的健康点数还会受到后⾯的路径的影响。也就是从上往下的状态转移不能很好地解决问题。 这个时候我们要换⼀种状态表示从 [i, j] 位置出发到达终点时所需要的最低初始健康点数。这样我们在分析状态转移的时候后续的最佳状态就已经知晓。 综上所述定义状态表示为 dp[i][j] 表示从 [i, j] 位置出发到达终点时所需的最低初始健康点数。
状态转移方程 对于 dp[i][j] 从 [i, j] 位置出发下⼀步会有两种选择为了⽅便理解设 dp[ i ][ j ] 的最终答案是 x 走到右边然后⾛向终点 。那么我们在 [i, j] 位置的最低健康点数加上这⼀个位置的消耗应该要大于等于右边位 置的最低健康点数也就是 x dungeon[i][j] dp[i][j 1] 。 通过移项可得 x dp[i][j 1] - dungeon[i][j] 。因为我们要的是最小值因此这种情况下的 x dp[i][j 1] - dungeon[i][j] ⾛到下边然后⾛向终点。那么我们在 [i, j] 位置的最低健康点数加上这⼀个位置的消耗应该要⼤于等于下边位置的最低健康点数也就是 x dungeon[i][j] dp[i 1][j] 。 通过移项可得 x dp[i 1][j] - dungeon[i][j] 。因为我们要的是最小值因此这种情况下的 x dp[i 1][j] -dungeon[i][j] 综上所述我们需要的是两种情况下的最⼩值因此可得状态转移⽅程为 dp[i][j] min(dp[i 1][j], dp[i][j 1]) - dungeon[i][j] 但是如果当前位置的 dungeon[i][j] 是⼀个⽐较⼤的正数的话 dp[i][j] 的值可能变成 0 或者负数。也就是最低点数会⼩于 1 那么骑⼠就会死亡。因此我们求出来的 dp[i][j] 如果⼩于等于 0 的话说明此时的最低初始值应该为 1 。处理这种情况仅需让 dp[i][j] 与 1 取⼀个最⼤值即可 dp[i][j] max(1, dp[i][j])。 初始化防止填表时不越界 在 dp 表最后⾯添加⼀⾏并且添加⼀列后所有的值都先初始化为⽆穷⼤然后让 dp[m][n - 1] dp[m - 1][n] 1 即可。 填表顺序 根据「状态转移⽅程」我们需要「从下往上填每⼀⾏」「每⼀⾏从右往左」。 返回值 根据「状态表⽰」我们需要返回 dp[0][0] 的值。 代码实现 class Solution {
public:int calculateMinimumHP(vectorvectorint dungeon) {int m dungeon.size();int n dungeon[0].size();vectorvectorint dp(m1, vectorint(n1,INT_MAX));// 初始化dp[m][n-1] dp[m-1][n] 1;// 填表for (int i m - 1; i 0; i--){for (int j n - 1; j 0; j--){dp[i][j] min(dp[i1][j],dp[i][j1]) - dungeon[i][j];dp[i][j] max(1,dp[i][j]); // 防止正数太大}}return dp[0][0];}
};
