赞
踩
是什么?dp表里的值所表示的含义就是状态表示
dp[i][j]表示:从[i,j]w位置出发,到达终点,所需的最低初始健康点数
dp[i]等于什么
计算从该位置到终点需要的最低健康点数
可以往下走和往右走,所以分为两种情况
保证填表的时候不越界
在最下和最右添加一列
算dp[i,j]时要用到下边和右边的值,所以不能让多出来的虚拟节点干扰正确结果
为了填写当前状态的时候,所需要的状态已经计算过了
从下往上,从右往左
题目要求+状态表示
dp[0][0]
- class Solution {
- public:
- int calculateMinimumHP(vector<vector<int>>& dungeon) {
-
- int m = dungeon.size();
- int n = dungeon[0].size();
- //1.创建dp表
- vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
- //2.初始化
- dp[m][n-1] = dp[m-1][n] = 1;
- //3.填表
- for(int i = m-1;i >=0;i--)
- {
- for(int j = n-1;j >=0;j--)
- {
- dp[i][j] = min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j];
- dp[i][j] = max(1,dp[i][j]);
- }
- }
- //4.返回值
- return dp[0][0];
- }
- };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。