威伦特

一道常规的动态规划题目。ㅤ ㅤ ㅤ ㅤ ㅤ

基于题目：我们不妨逆向思考，从终点开始行动一直到起点
根据题目例子进行分析
​

首先我们新创建一个二维数组，大小和原数组相同，将所需要最少的“血”储存在这个数组中

    int row=dungeon.size();
	int col=dungeon[0].size(); 
	vector<vector<int>>dp(row+1,vector<int>(col+1,0));

P为-5 也就是说在P点的时候至少需要6才行，但是P也有可为+/- 所以我们需要进行判定

 dp[row-1][col-1]=(dungeon[row-1][col-1]>=0?1:1-dungeon[row-1][col-1]);

也就是说如果P大于0的话 其实就只需要1 就可以了 小于0的话需要1-P

骑士行走 为右和下，

因此可以得出动态规划表达式

Dp[i][j]=max(1,min(dp[i][j+1],dp[i+1][j])-dungeon[i][j]);

也就是说：取dp右边和下边的最小值减去其本身的值 和1比较 取最大的值

有了表达式于是我们可以进行动态规划了

首先在数组边缘进行dp取值

​

目的是为了获得

 dp[i+1][j]和dp[i][j+1]

，避免数组越界

取得的值如下

取值规则如下：

当为负数的时候 直接相加绝对值

当为正数的时候 减去值 如果减去结果小于1 则说明至少需要1滴血才能到达 于是值设置为1

于是我们接下来就直接使用表达式就可以了

 for(int i=row-2;i>=0;i--)
{
	for(int j=col-2;j>=0;j--)
	{
	    int len=(min(dp[i+1][j],dp[i][j+1]));
		dp[i][j]=max(1,len-dungeon[i][j]);
	}
}

​

然后返回

dp[0][0]

就是骑士到达终点所需要最小的值了！