动态规划算法:10.路径问题_地下城游戏_C++

 目录

题目链接:174. 地下城游戏 - 力扣(LeetCode)

一、题目解析

题目:​编辑

解析:

二、算法原理

1、状态表示

2、状态转移方程

状态转移方程推理:

3、初始化

dp表初始化:

特殊位置初始化:

4、填表顺序

5、返回值

三、编写代码


题目链接:174. 地下城游戏 - 力扣(LeetCode)

一、题目解析

题目:

解析:

  我们由题目可以知道,我们骑士的最低血量就是我们要求得最小初始值,我们要求骑士拯救公主后血量在0以上,那么最小的时候是什么情况:

  • 如果拯救公主时,有守卫守护,那么我们希望拯救完公主后,血量为1
  • 如果拯救公主时,没有首位守护,或者有健康点数可以增加,那么我们希望拯救公主前,血量为1

并且在以上过程中,骑士的血量不可以降至0或者0以下

二、算法原理

1、状态表示

我们在状态标识的时候,一般都会创建一个数组dp,也就是我们所说的dp表,我们要做的就是把每一个状态的值填入这个表内,最终这个表内的某一个值可能就是我们要返回的值。 

  状态简单理解就是dp表内某一个值代表的含义。

如何确定状态表示

  • 题目要求

   简单的题目里一般会给出

  • 经验+题目要求

  越学越深入,动态规划也是熟能生巧,在题目中没有明显给出的时候,我们就要凭借自己做题的经验来确定,所以就需要我们大量的做题。

  • 分析问题的过程中,发现重复子问题

 分析问题的过程中把重复子问题抽象成我们的状态表示,这个更难理解,一切的基础都是我们先对动态规划算法熟练运用。我也不懂,我们慢慢来。

综上:我们通常会以一个位置为结尾或者开始求得我们想要的答案

那我们的这道题得状态表示是什么样的:

根据经验,我们在此以一个位置为开始解题

为什么这次我们以一个位置为开始,但是之前都是以一个位置为结尾呢?

如果以一个位置为结尾解题,那么该点应该表示,到达该位置时需要的最小生命值,那么如果下一个位置的值是一个负数呢?我们只能保证通过该位置,但是并不能保证安全通过下一个位置,所以我们以一个位置为开始解题,也就是从该位置开始,到达终点所需要的最小生命值

状态表示:dp[i][j]表示,从(i,j)位置开始,到达终点所需要的最小生命值

2、状态转移方程

 确定状态表示之后我们就可以根据状态标识推出状态转移方程

  状态转移方程是什么?

不讲什么复杂的,简单来说状态转移方程就是    dp[i][j]等于什么 dp[i][j]=?

  这个就是状态转移方程,我们要做的,就是推出dp[i][j]等于什么

  我们根据状态表示再结合题目+经验去推理转移方程,这一步也是我们整个解题过程中最难的一步

  我们在这道题先简单了解下什么是状态转移方程,之后比较难的题目再细推

状态转移方程推理:

  我们考虑从右下往左上进行动态规划。令 dp[i][j] 表示从坐标 (i,j) 到终点所需的最小初始值。换句话说,当我们到达坐标 (i,j) 时,如果此时我们的路径和不小于 dp[i][j],我们就能到达终点

  这样一来,我们就无需担心路径和的问题,只需要关注最小初始值。对于 dp[i][j],求从位置(i,j)到达终点的最小值,我们只要关心 dp[i][j+1] 和 dp[i+1][j] 的最小值 min,减去(i,j)位置的值,就是我们所求的dp[i][j]了,同时,初始值还必须大于等于 1。这样我们就可以得到状态转移方程:

状态转移方程:dp[i][j]=max(min(dp[i+1][j],dp[i][j+1])−(i,j)位置的值,1)

3、初始化

 我们创建dp表就是为了把他填满,我们初始化是为了防止在填表的过程中越界

怎么谈越界?

dp表初始化:

如果我们的dp表创建成与原表大小相同,那么在处理最后一个值时,其根本没有dp[i][j+1]与dp[i+1][j],这就会造成越界,不仅如此,我们dp表的最后一行,也不会有dp[i+1][j],dp表的最后一列,也不会有dp[i][j+1]

所以我们就需要额外的增加一行一列,来保证我们填表的时候不越界

  我们在对整个dp表初始化时,我们不能让新增的值影响原有数据填表,根据状态方程我们知道,新增的值会与原数据进行一个比较,从而选择较小的那个,所以我们在整体初始化时,把所有的值初始化为INT_MAX,这样就不会影响了。

特殊位置初始化:

  我们填表的第一个值是原数据的最后一个值,也就是公主所在的位置,此时,其dp[i][j+1]与dp[i+1][j]都是INT_MAX,并没有原数据在其中比较,所以根据状态转移方程我们知道,如果都是INT_MAX的话,该位置最终也会是INT_MAX,最终影响填表。该位置就是终点,这个位置的如果是正数的话,其dp值应该为1,如果是负数,那么它的dp值应该是(1-该位置的值)。所以为了保证该位置填表正确,不影响之后填表,我们需要把其dp[i][j+1]和dp[i+1][j]设置为1即可。

4、填表顺序

从下到上,从右到左依次填表

5、返回值

dp表的第一个值,也就是dp[0][0]

三、编写代码

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& d) {
  int m =d.size(),n=d[0].size();
//1、创建dp表
  vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
//2、特殊位置初始化
  dp[m-1][n]=1;
  dp[m][n-1]=1;
//3、填表
  for(int i=m-1;i>=0;i--)
  {
    for(int j=n-1;j>=0;j--)
    {
//这里我将状态转移方程拆开来写了
        dp[i][j]=min(dp[i][j+1],dp[i+1][j])-d[i][j];
        dp[i][j]=max(dp[i][j],1);
    }
  }
//4、返回值
  return dp[0][0];

    }
};

上一篇:微信小程序-数据模型与动态赋值


下一篇:Oracle可编辑视图