【算法】【递归与动态规划模块】最小通关血量

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定一个矩阵作为骑士需要经过的地图map，从左上角出发，终点为右下角，其中矩阵中的数值都是整数值，对于每一个格子，如果当前格子是正数说明骑士可以加血，如果是负数说明骑士会减血，到终点的过程中骑士血量不能为0，最少血量为1，否则会死亡，求骑士到右下角最少在左上角需要多少血量。
如：
$\left[\begin{array}{ccc}-2& -3& 3\\ -5& -10& 1\\ 0& 30& -5\end{array}\right]$
map如上矩阵，骑士最少的血量为7才能保持过程中不死。

解决方案

原问题：
经典动态规划版本：
1、dp[i][j]表示从map[i][j] 到右下角时最小需要多少血量。
2、递推关系：dp[i][j] 只能往前走和往下走，所以dp[i][j]所需要的最少血量应该 Min(dp[i+1][j], dp[i][j+1]) - map[i][j] > 0 ? Min(dp[i+1][j], dp[i][j+1]) - map[i][j] : 1;

代码编写

java语言版本

原问题：
动态规划：

    /**
     * 二轮：经典动态规划
     * @param map
     * @return
     */
    public static int minHpCP(int[][] map) {
        if (map == null || map.length == 0 || map[0].length == 0) {
            return 0;
        }
        int row = map.length;
        int col = map[0].length;
        int[][] dp = new int[row][col];
        dp[row-1][col-1] = 1 - map[row-1][col-1] > 0 ? 1 - map[row-1][col-1] : 1;
        for (int i = row-2; i >= 0; i--) {
            dp[i][col-1] = dp[i+1][col-1] - map[i][col-1] > 0 ? dp[i+1][col-1] - map[i][col-1] : 1;
        }
        for (int j = col-2; j >= 0; j--) {
            dp[row-1][j] = dp[row-1][j+1] - map[row-1][j] > 0 ? dp[row-1][j+1] - map[row-1][j] : 1;
        }
        for (int i = row-2; i >= 0; i--) {
            for (int j = col-2; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i+1][j], dp[i][j+1]) - map[i][j] > 0 ? Math.min(dp[i+1][j], dp[i][j+1]) - map[i][j] : 1;
            }
        }
        return dp[0][0];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

动态规划降低空间版本：

    /**
     * 二轮：动态规划降低空间复杂度版本
     * @param map
     * @return
     */
    public static int minHPCPReduceMem(int[][] map) {
        if (map == null || map.length == 0 || map[0].length == 0) {
            return 0;
        }
        int row = map.length;
        int col = map[0].length;
        int[] dp = new int[col];
        dp[col-1] = 1 - map[row-1][col-1] > 0 ? 1 - map[row-1][col-1] : 1;
        for (int j = col-2; j >= 0; j --) {
            dp[j] = dp[j+1] - map[row-1][j] > 0 ? dp[j+1] - map[row-1][j] : 1;
        }
        for (int i = row-2; i >= 0; i--) {
            // 每一行先初始化第一个
            dp[col-1] = dp[col-1] - map[i][col-1] > 0 ? dp[col-1] - map[i][col-1] : 1;
            for (int j = col-2; j >= 0 ; j--) {
                dp[j] = Math.min(dp[j], dp[j+1]) - map[i][j] > 0 ? Math.min(dp[j], dp[j+1]) - map[i][j] :1;
            }
        }
        return dp[0];
    }

    public static void main(String[] args) {
        System.out.println(minHPCPReduceMem(new int[][]{
                {-2, -3, 3},
                {-5, -10, 1},
                {0, 30, -5}
        }));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这道题和前面不一样的地方在于dp需要倒着计算，从终点开始计算，第二个注意的地方就是递推的逻辑，正常来说应该要满足一个表达式就是 dp[i][j] + map[i][j] >= Min(dp[i][j+1], dp[i+1][j]), 这样才能够刚刚好过当前关卡，如果说血量溢出的情况下记得最少血量需要调整到1，否则答案可能会过多。

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！