fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
动态规划帮我通关了《魔塔》 :: labuladong的算法小抄
交作业~数组迭代自底向上如下
public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length;
int n = dungeon[0].length;
int[][] dp = new int[m + 1][n + 1];
dp[m - 1][n - 1] = dungeon[m - 1][n - 1] < 0 ? -dungeon[m - 1][n - 1] + 1 : 1;
for (int i = m; i >= 0; i--) {
for (int j = n; j >= 0; j--) {
if (i == m || j == n) {
dp[i][j] = Integer.MAX_VALUE;
continue;
}
if (i == m - 1 && j == n - 1) {
continue;
}
int res = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
dp[i][j] = res <= 0 ? 1 : res;
}
}
return dp[0][0];
}
状态压缩如下：
public int calculateMinimumHPII(int[][] dungeon) {
int m = dungeon.length;
int n = dungeon[0].length;
int[] dp = new int[n + 1];
for (int i = m; i >= 0; i--) {
for (int j = n; j >= 0; j--) {
if (i == m || j == n) {
dp[j] = Integer.MAX_VALUE;
continue;
}
if (i == m - 1 && j == n - 1) {
dp[j] = dungeon[i][j] < 0 ? -dungeon[i][j] + 1 : 1;
continue;
}
int res = Math.min(dp[j], dp[j + 1]) - dungeon[i][j];
dp[j] = res <= 0 ? 1 : res;
}
}
return dp[0];
}
如果定一个 dp[i][j][2]：dp[i][j][0]代表[0][0]到[i][j]的血量，dp[i][j][1]:代表从[0][0]到[i][j]的最少血量 简单描述：记录两个参数：此时的血量，需要最少的血瓶 能否得出正确答案
@SunnyXiaoWei 不行，dp[i][j]选择dp[i-1][j]和dp[i][j-1]中需要最少血瓶的路径不一定是对的，如[[1,-3,3],[0,-2,0],[-3,-3,-3]]。这种办法只能通过40/45
交作业~数组迭代自底向上如下
public int calculateMinimumHP(int[][] dungeon) { int m = dungeon.length; int n = dungeon[0].length; int[][] dp = new int[m + 1][n + 1]; dp[m - 1][n - 1] = dungeon[m - 1][n - 1] < 0 ? -dungeon[m - 1][n - 1] + 1 : 1; for (int i = m; i >= 0; i--) { for (int j = n; j >= 0; j--) { if (i == m || j == n) { dp[i][j] = Integer.MAX_VALUE; continue; } if (i == m - 1 && j == n - 1) { continue; } int res = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]; dp[i][j] = res <= 0 ? 1 : res; } } return dp[0][0]; }状态压缩如下：
public int calculateMinimumHPII(int[][] dungeon) { int m = dungeon.length; int n = dungeon[0].length; int[] dp = new int[n + 1]; for (int i = m; i >= 0; i--) { for (int j = n; j >= 0; j--) { if (i == m || j == n) { dp[j] = Integer.MAX_VALUE; continue; } if (i == m - 1 && j == n - 1) { dp[j] = dungeon[i][j] < 0 ? -dungeon[i][j] + 1 : 1; continue; } int res = Math.min(dp[j], dp[j + 1]) - dungeon[i][j]; dp[j] = res <= 0 ? 1 : res; } } return dp[0]; }
这个代码的最核心的就是要从后往前，然后 要对base case 也就是最后一行和最后一列进行维护， 要和 m n 的 MAX_VALUE进行比较 ， （ps: 代码写的真tm的规范！！！👍）
@SunnyXiaoWei 并不行，一开始我也是这么做的，但是后面会发现你在选择的时候并不知道用血量转还是用到达该位置的最小初始值转，如果要做可能需要在你这个基础上再加一维存放来自左边和上方的那个三维数组，那就是4维了
倒着走 + 优势抹平
考虑两个场景， 6 -> -5 ， 和 9 -> -5， 两个场景都可以活着，9比6并没有优势，所以应该优势抹平，走过去之后hp置为0（含义就是走到最后一格，血量为1就行，多了没用，多多少也无所谓，干脆遍历的时候扣除多余血量便于计算）
备忘录借用入参
public int calculateMinimumHP(int[][] dungeon) {
// 倒着走，看一下最后在起点处， hp 最低是多少
for (int i = dungeon.length - 1; i >= 0; i--) {
for (int j = dungeon[i].length - 1; j >= 0; j--) {
if (i == dungeon.length-1 && j == dungeon[i].length - 1) {
dungeon[i][j] = dungeon[i][j]
} else if(i == dungeon.length-1) {
int right = dungeon[i][j+1];
dungeon[i][j] = right+ dungeon[i][j];
} else if(j == dungeon[i].length - 1) {
int down = dungeon[i+1][j] ;
dungeon[i][j] = down+ dungeon[i][j];
} else {
int right = dungeon[i][j+1] ;
int down = dungeon[i+1][j] ;
// 选hp多的那条路（也就是扣的少的那条路，因为hp都是负的或者0）
dungeon[i][j] = Math.max(right, down) + dungeon[i][j];
}
// 多余的 hp 没有意义，
// 追求的是 最小起始hp，不是到达hp，所以 hp 够用就行，多了没用，
// 考虑两个场景， 6 -> -5 ， 和 9 -> -5， 两个场景都可以活着，9比6并没有优势，所以应该优势抹平，置为0
if (dungeon[i][j] > 0) {
dungeon[i][j] = 0;
}
}
}
int min = dungeon[0][0];
if (min >= 0) {
return 1;
}
return -min+1;
}
JS版本
/**
* @param {number[][]} dungeon
* @return {number}
*/
var calculateMinimumHP = function (dungeon) {
const n = dungeon.length;
const m = dungeon[0].length;
const dp = Array(n + 1).fill(0).map(_ => Array(m + 1).fill(0));
// dp[i][j] 表示 从 (i,j) 到 终点 (n,m)所需要的最小血量
for (let i = 0; i <= n; i++) dp[i][m] = Number.MAX_SAFE_INTEGER;
for (let j = 0; j <= m; j++) dp[n][j] = Number.MAX_SAFE_INTEGER;
let res;
// 反着遍历 求0,0
for (let i = n-1; i >= 0; i--) {
for (let j = m-1; j >= 0; j--) {
if (i == n-1 && j == m-1) {
// 最后一个格子 是否会掉血？ 有血瓶或者啥都没有的时候 其实只需要留一滴血就行了
// 如果有掉血的怪物 那么最少血量就是怪物的伤害+1
dp[i][j] = dungeon[i][j] > 0 ? 1 : -dungeon[i][j] + 1;
} else {
// 计算 看看下发和右方 取最小的 减去当前格子的数值
res = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
// 如果是正数(1- (-1)) 说明遇上了怪物 血量要是res才可以抗下 如果是负数 说明遇上了血瓶 只需要保证1点血即可
dp[i][j] = res <= 0 ? 1 : res;
}
}
}
return dp[0][0]
};
Dont you get the same bugs if dp(0, 1) = 2, dp(1, 0) = 2?? I dont see how the second method can avoid the same situation... please help, I have been thinking about it for a week :(
if (i == 0 && j == 0) {
// 保证骑士落地不死就行了
return gird[i][j] > 0 ? 1 : -grid[i][j] + 1;
}
各位大佬，gird[i][j] > 0 的条件下为啥要返回1，不应该返回0也可以吗？这个地方没看明白
11 行 DP 代码（空间压缩、自底向上）
/**
* @param {number[][]} dungeon
* @return {number}
*/
var calculateMinimumHP = function (dungeon) {
const h = dungeon.length, w = dungeon[0].length;
let dp = new Array(w + 1).fill(Infinity);
for (let i = h - 1; i >= 0; --i) {
for (let j = w - 1; j >= 0; --j) {
if (i === h - 1 && j === w - 1) dp[j] = 0; // base case
dp[j] = Math.max(0, -dungeon[i][j] + Math.min(dp[j + 1], dp[j]));
}
}
return dp[0] + 1;
};
自底向上的迭代方法(省去了数组越界判断）
int calculateMinimumHP(int[][] grid) {
int m = grid.length, n = grid[0].length;
// dp[i][j]表示从grid[i][j]到grid[m-1][n-1]所需的最低血量
int[][] dp = new int[m+1][n+1];
// 初始化基本状态
// 省去数组越界的判断
for (int i = 0; i <= m; i++) {
dp[i][n] = Integer.MAX_VALUE;
}
for (int j = 0; j <= n; j++) {
dp[m][j] = Integer.MAX_VALUE;
}
// base case
dp[m-1][n-1] = grid[m-1][n-1] >= 0? 1: -grid[m-1][n-1] + 1;
// 进行循环
for (int i = m-1; i >= 0; i--) {
for (int j = n-1; j >= 0; j--) {
// 不要计算dp[m-1][n-1]的值
if (i == m-1 && j == n-1) {
continue;
}
// 状态转移方程
int tem = Math.min(dp[i][j+1], dp[i+1][j]) - grid[i][j];
dp[i][j] = tem > 0 ? tem: 1;
}
}
return dp[0][0];
}
Swift版本-迭代方式
尝试一下
func calculateMinimumHP(_ dungeon: [[Int]]) -> Int {
let rows = dungeon.count, cols = dungeon[0].count
var dp: [[Int]] = .init(repeating:
.init(repeating: Int.max, count: cols)
, count: rows)
/// 初始化`Base Case`
dp[rows - 1][cols - 1] = dungeon[rows - 1][cols - 1] > 0
? 1
: -dungeon[rows - 1][cols - 1] + 1
/// 根据`Base Case`倒序初始化 最后一列数据
for row in stride(from: rows - 2, through: 0, by: -1) {
let value = dp[row + 1][cols - 1] - dungeon[row][cols - 1]
dp[row][cols - 1] = value > 0 ? value : 1
}
/// 根据`Base Case`倒序初始化 最后一行数据
for col in stride(from: cols - 2, through: 0, by: -1) {
let value = dp[rows - 1][col + 1] - dungeon[rows - 1][col]
dp[rows - 1][col] = value > 0 ? value : 1
}
/// 迭代 推导至 `dp[0][0]`
for row in stride(from: rows - 2, through: 0, by: -1) {
for col in stride(from: cols - 2, through: 0, by: -1) {
/// 状态转移方程
var value = min(
dp[row][col + 1], dp[row + 1][col]
) - dungeon[row][col]
value = value > 0 ? value : 1
dp[row][col] = value
}
}
return dp[0][0]
}
外部初始化 使用二维 DP数组
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length;
int n = dungeon[0].length;
//dp[i][j] 从i ，j 位置到达 刚好能 到达终点的最低健康点数
int[][] dp = new int[m+1][n+1];
/*
表示如果出生在 最终节点位置
如果末尾位置有个血包，则至少需要1
如果末尾位置有个怪物，则至少需要 怪物攻击力 + 1 才能保证死不了
*/
dp[m-1][n-1] = dungeon[m-1][n-1] >= 0 ? 1 : -dungeon[m-1][n-1]+1;
for(int j = 0; j<=n;j++){
dp[m][j] = Integer.MAX_VALUE;
}
for(int i = 0; i<=m;i++){
dp[i][n] = Integer.MAX_VALUE;
}
for(int i = m-1 ; i>=0;i--){
for(int j = n-1;j>=0;j--){
if(i == m-1 && j==n-1){
continue;
}
/*
从右边 / 下边转移到 i j 选择其中较小的值
从i j 到 右边 / 下边是 加上 dungeon[i][j] 之后才会转移过去的， 所以从右边/下边 转移到i j 则需要 减去 dungeon[i][j]
*/
int temp = Math.min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j];
//因为如果当前位置有 怪物 则至少保证 扣血之后 需要剩余1点
dp[i][j] = temp <= 0 ? 1 : temp;
}
}
return dp[0][0];
}
}
我这个挺容易理解的
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length;
int n = dungeon[0].length;
int[][] dp = new int[m][n];
dp[m-1][n-1] = (dungeon[m-1][n-1]>=0)?1:1-dungeon[m-1][n-1];
//右边界
for(int i = m-2;i>=0;i--){
dp[i][n-1] = (dp[i+1][n-1]-dungeon[i][n-1]<=0)?1:dp[i+1][n-1]-dungeon[i][n-1];
}
//下边界
for(int i = n-2;i>=0;i--){
dp[m-1][i] = (dp[m-1][i+1] - dungeon[m-1][i]<=0)?1:dp[m-1][i+1] - dungeon[m-1][i];
}
//遍历根据递推公式和初始条件可知,应当从下往上,从右往左去遍历
for(int i = m-2;i>=0;i--){
for(int j = n-2;j>=0;j--){
dp[i][j] = (Math.min(dp[i][j+1],dp[i+1][j])-dungeon[i][j]<=0)?1:Math.min(dp[i][j+1],dp[i+1][j])-dungeon[i][j];
}
}
return dp[0][0];
}
}
从后往前推导， 如果还是不理解的话 ， 可以反转一下 按照传统的 从前往后推导试试看
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length;
int n = dungeon[0].length;
//dp[i][j] 表示从 i-1 , j-1 开始 刚好到达 终点 至少需要的健康点数
//转换从 dp[i+1][j] dp[i][j+1] 转换到dp[i][j]
int[][] dp = new int[m+1][n+1];
//如果落地就是 终点 ， 需要保证勇士至少一滴血活着
if(dungeon[m-1][n-1] >=0){
dp[m-1][n-1] = 1;
}else{
dp[m-1][n-1] = -dungeon[m-1][n-1] + 1;
}
//最后一行与最后一列
//因为前面的是要选一个最小的 所以 都初始化成 MAX_VALUE;
dp[m][n] = Integer.MAX_VALUE;
for(int i = 0; i<= m; i++){
dp[i][n] = Integer.MAX_VALUE;
}
for(int j = 0; j<= n; j++){
dp[m][j] = Integer.MAX_VALUE;
}
for(int i = m-1 ; i>=0 ; i--){
for(int j = n-1; j>=0 ; j--){
//这个位置是终点位置 前面已经初始化过了
if(i== m-1 && j == n-1){
continue;
}
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];
}
}
C++
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int m = dungeon.size(), n = dungeon[0].size();
vector<int> dp(n);
dp[n - 1] = dungeon[m - 1][n - 1] >= 0 ? 1 : -dungeon[m - 1][n - 1] + 1;
for (int i = n - 2; i >= 0; --i) {
if (dp[i + 1] - dungeon[m - 1][i] > 0)
dp[i] = dp[i + 1] - dungeon[m - 1][i];
else
dp[i] = 1;
}
for (int i = m - 2; i >= 0; --i) {
if (dp[n - 1] - dungeon[i][n - 1] > 0)
dp[n - 1] = dp[n - 1] - dungeon[i][n - 1];
else
dp[n - 1] = 1;
for (int j = n - 2; j >= 0; --j) {
if (min(dp[j], dp[j + 1]) - dungeon[i][j] > 0)
dp[j] = min(dp[j], dp[j + 1]) - dungeon[i][j];
else
dp[j] = 1;
}
}
return dp[0];
}
};
交个作业
public class leetcode_174 {
int calculateMinimumHP(int[][] grid){
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[m-1][n-1] = grid[m-1][n-1] >= 0 ? 1 : -grid[m-1][n-1] + 1;
for (int i = m-2; i >= 0; i--) {
int res = dp[i+1][n-1] - grid[i][n-1];
dp[i][n-1] = res <= 0 ? 1 : res;
}
for (int i = n-2; i >= 0 ; i--) {
int res = dp[m-1][i+1] - grid[m-1][i];
dp[m-1][i] = res <= 0 ? 1 : res;
}
for (int i = m-2; i >= 0; i--) {
for (int j = n-2; j >= 0; j--) {
int res = Math.min(dp[i+1][j], dp[i][j+1]) - grid[i][j];
dp[i][j] = res <= 0 ? 1 : res;
}
}
return dp[0][0];
}
}
