欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode174. 地下城游戏——动态规划的无后效性

程序员文章站 2022-06-30 20:47:51
...

引入

今天的每日一题174. 地下城游戏一眼看上去就是使用dp,并且是非常标准的DP场景。

我一开始是这样做的:

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int M=dungeon.length;
        int N=dungeon[0].length;

        int[][] dp=new int[M+1][N+1];
        //初始值dp[0][0]=0;
        for (int[] d:dp){
            Arrays.fill(d,Integer.MIN_VALUE);
        }
        dp[0][1]=1;
        dp[1][0]=1;
        //记录整个过程的最小值
        int min=Integer.MAX_VALUE;
        for (int i=0;i<M;i++){
            for (int j=0;j<N;j++){
                dp[i+1][j+1]=Math.max(dp[i+1][j],dp[i][j+1])+dungeon[i][j];
                if (dp[i+1][j+1]<min) min=dp[i+1][j+1];
            }
        }
        return -min+1;
    }
}

然而这样做是不对的,如果按照从左上往右下的顺序进行动态规划,对于每一条路径,我们需要同时记录两个值。第一个是「 从出发点到当前点的路径和 dp」,第二个是「 从出发点到当前点所需的最小初始值 min」,准确的来说是从出发点到当前点的所有可能的通路上的最小值。

而这两个值的重要程度相同,因为当前路径和的最大值,并不一定产生最小的那个生命初始值。来看下面这个例子:
Leetcode174. 地下城游戏——动态规划的无后效性
路径和在0/-2/3/0上取到最大,值为1;
但是初始生命值在0/-1/0/0上取到最小,值为2。

所以,这个时候很难去取舍到底选择哪条路径,因为两个信息是同等重要的。

如果问直接选择最小生命值的那条线不就行了?这是不对的。我们来看整体,这种贪心方法即0/-1/-3/-3/-2,最小生命值是10;而考虑全局,最小生命值只需要是3,也就是0/-2/3/0/-2的这条线。

所以,在两个信息同等重要的情况下,是不满足动态规划的无后效性的。

因为有两个重要程度相同的参数同时影响后续的决策。也就是说,这样的动态规划是不满足「无后效性」的。

本题解法

于是我们考虑从右下往左上进行动态规划,反过来考虑就能解决上面这个难题。

先贴代码再解释:

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int M = dungeon.length;
        int N = dungeon[0].length;

        int[][] dp = new int[M + 1][N + 1];
        for (int[] d:dp){
            Arrays.fill(d,Integer.MAX_VALUE);
        }
        dp[M][N-1]=1;
        dp[M-1][N]=1;//初始生命值1

        //倒过来考虑(从后往前)
        for (int i=M-1;i>=0;i--){
            for (int j=N-1;j>=0;j--){
                dp[i][j]=Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
                //血量小于0,说明(从前往后)走不会出现负数,可以重置为1
                if (dp[i][j]<=0) dp[i][j]=1;
            }
        }
        return dp[0][0];
    }
}

从后往前,也就是从右下到左上不用再去考虑选择哪条最大和的路径了,而只需要去关注哪条路径下需要最小生命值。为什么倒过来会产生这样的效果呢?

先来看看dp的状态转移方程:
dp[i][j]=Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
这个很好理解,就是每一次找两条路径下的最小的生命值,如果最小生命值是负数,那么就赋值为1,这个原因也很好理解,我们是从后往前推的,那么从前往后推,从这格开始,向后的路都会是正的血量,所以之前算的最小生命值就不成立。

倒过来考虑后,会发现去考虑哪条路径是最大和的这个信息消失了,而保留了最小生命值这个信息。因为从后往前推,dp[i][j]表示从(i,j)出发,一定是能够到达终点的(因为我们本来就是从终点出发的)。最关键的一点,从前往后和从后往前上,找最低生命值的方式是不同的:

  1. 从前往后推,找最低生命值需要去考虑在合适的路径上找到最小生命值,但是不能以最小生命值来贪心。如果以最小生命值来贪心,我们贪心的方式是找每一格上最小的值。
  2. 从后往前推,找最低生命值的贪心策略是找每一格上最大的值(题解中取了负数,所以找的是最小值)。

注:这里的贪心并不是说的贪心算法,而是说的动态规划时的思考原则:在每一格做出的贪心选择,也就是状态转移的方式。

再来看这个图捋一遍:
Leetcode174. 地下城游戏——动态规划的无后效性

  1. 从前往后的dp策略:
    我们会将0/-1/-3/-3/-2作为最终答案的路径,这样保证了动态规划中贪心的策略是找到最小的生命值。但是这个生命值虽然是最小的,但不是最合适的最小生命值。
    我们要找的最小生命值,应该是所有路径上的最小生命值。
  2. 从后往前的dp策略:
    我们会讲0/-2/3/0/-2最为最终答案的路径,这样我们找的是使得生命值尽可能大的格子。比如一开始在-2,下一步应该是去0,而不是去-3,因为选择0,我们只需要初始生命值是3,就可以从0到-2;而选择-3,初始生命值则需要6。

本题感悟

遇到多信息的动态规划题目的时候,先去判断这些信息是否有优先级:具体判断条件就是将每一个信息作为最优先的条件来找反例。

在信息同等重要的前提下,考虑从后往前的动态规划。

相关标签: LeetCode