赞
踩
https://leetcode-cn.com/problems/dungeon-game/
要保证骑士的血量最后最少,所以到达P的时候,血量为1,所以我们逆向考虑。因为每次只能向右或者向下走,很容易想到动态规划。设置一个数组dp[i][j]表示从(i,j)开始到终点需要的最少血量。
对于 dp[i][j],我们只要关心 dp[i][j+1]和 dp[i+1][j] 的最小值 。
状态转移方程:dp[i][j] = min( dp[i+1][j], dp[i][j+1]) - dungeon[i][j];
注意:如果dp[i][j] <=0必须要让dp[i][j]=1,骑士不能死亡(想半天没想到。。。)
- class Solution {
- public int calculateMinimumHP(int[][] dungeon) {
- int[][] dp = dungeon;
- int d = dungeon[0].length;
- int h = dungeon.length;
- for (int i = h-1; i >= 0; i--) {
- for (int j = d-1; j >= 0; j--) {
- if(i==h-1 && j==d-1) dp[i][j] = 1 - dungeon[i][j];
- else if(i==h-1) dp[i][j] = dp[i][j+1] - dungeon[i][j];
- else if(j==d-1) dp[i][j] = dp[i+1][j] - dungeon[i][j];
- else dp[i][j] = Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j];
- if(dp[i][j] <= 0) dp[i][j] = 1;
- }
- }
- return dp[0][0];
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。