完美世界-第2道算法题目-黄金圣斗士欧洛斯要去圣域救雅典娜

这道题与Leetcode的第62题目类似，有兴趣的同学可以查看下：都属于动态规划的题目。
https://www.nowcoder.com/discuss/188537
* 题目介绍：完美世界-第2道算法题目
     * 黄金圣斗士欧洛斯要去圣域救雅典娜，需要从左上角出发，每次只能向右或向下走，最后达到右下角见到雅典娜。
     * 地图的每个位置的值代表圣斗士要遭遇的事情，如果是负数，说明此处有阻击，要让圣斗士损失血量，如果是非负数，
     * 代表次数有血瓶，能让圣斗士回血。圣斗士从左上角走到右下角的过程中，走到任何一个位置时，血量都不少于1，
     * 为了保证圣斗士能救出雅典娜，初始血量至少是多少？地图为一个二维数组map，如下矩阵。根据map，返回初始血量。
     * -2  -3 3
     * -5 -10 1
     * 0 30 -5
     * 初始血量至少为7。
     * 输入描述：一个n*m的二维数组。第一行：数组的行数n(n>0);第二行：数组的列数m(m>0);
     * 第三行：数组，每个位置的血量，行优先。
     * 输出描述：对于每个测试实例，要求输出初始血量。
     * 示例：
     * 输入：
     * 3
     * 3
     * -2 -3 3 -5 -10 1 0 30 -5
     * 输出：
     * 7
     * <p>
     * 特殊测试例子：如果经过的每个位置都是加血量，则初始血量也至少为1。
     * 思路分析:
     * 圣斗士是从左上角往右下角走，保证每一个位置(包括终点右下角)的血量都至少为1。
     * 欲求起始的最少血量，因此需要逆着推，从终点向起始点推导，且保证每个位置的血量至少为1。
     * 方法1:动态规划方法。
     * S1: 首先初始化：dp[rows - 1][cols - 1]、最后一列和最后一行。
     *      dp[rows-1][j]=max{(dp[rows-1][j+1]-blood[i][j]),1};
     *      dp[i][cols-1]=max{dp[i+1][cols-1]-blood[i][cols-1],1};
     * S2:计算其他位置
     *      dp[i][j] = max{(min{dp[i][j+1],dp[i+1][j]}-blood[i][j]),1};
     *      最后返回dp[0][0]即可。
     * 注释：max{1,x}的目的是保证到达该位置之前血量至少为1。
     * 方法2:递归方法。
     *  仍然利用dp数组保存到达该位置前需要的至少血量。
     *  递归方法：完成dp[i][j]的更新，并递归下一步。
     *  递归终止条件：①出了数组边界；②当前计算的血量不是最少的。
     *  实现：从(rows-1,cols-1)开始倒着推导，更新完当前至少血量后，后续有两种走法:向上或向左;
     *  运行完之后，所有位置的dp都被更新，返回dp[0][0]即可。
     */

    /**
     * 方法1: 动态规划
     */
    public int needMinBlood_DP(int[][] bloods) {
        if (bloods == null || bloods.length == 0) return 1;
        int rows = bloods.length, cols = bloods[0].length;
        //创建一个dp数组，dp[i][j]表示走到该位置需要的最少血量
        int[][] dp = new int[rows][cols];
        //S1:最后一列和最后一行dp初始化
        dp[rows - 1][cols - 1] = Math.max(1, 1 - bloods[rows - 1][cols - 1]);
        for (int i = rows - 2; i >= 0; i--)//对最后一列初始化
            dp[i][cols - 1] = Math.max(1, dp[i + 1][cols - 1] - bloods[i][cols - 1]);
        for (int j = cols - 2; j >= 0; j--)//对最后一行初始化
            dp[rows - 1][j] = Math.max(1, dp[rows - 1][j + 1] - bloods[rows - 1][j]);
        //S2:计算其他位置dp
        for (int i = rows - 2; i >= 0; i--) {
            for (int j = cols - 2; j >= 0; j--) {
                dp[i][j] = Math.max(1, Math.min(dp[i][j + 1], dp[i + 1][j]) - bloods[i][j]);
            }
        }
        printArray("各个位置需的最少的血量：", dp);
        return dp[0][0];
    }

    /**
     * 方法2:递归方法
     */
    public int needMinBlood(int[][] bloods) {
        if (bloods == null || bloods.length == 0) return 1;
        int rows = bloods.length, cols = bloods[0].length;
        //创建一个dp数组，到达该位置需要的最少血量,初始化为Integer的最大值
        int[][] needMinBloodDp = new int[rows][cols];
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                needMinBloodDp[i][j] = Integer.MAX_VALUE;
        //从右下角开始，remainBlood=1表示走完该(row,col)位置需要剩余的血量
        recursive(bloods, needMinBloodDp, rows - 1, cols - 1, 1);
        printArray("各个位置需的最少的血量：", needMinBloodDp);
        return needMinBloodDp[0][0];
    }

    /**
     * 递归方法
     */
    private void recursive(int[][] nums, int[][] needMinBloodDp, int row, int col, int remainBlood) {
        if (row < 0 || col < 0 || row >= nums.length || col >= nums[0].length
                || remainBlood - nums[row][col] >= needMinBloodDp[row][col])
            return;//边界条件+当前需要血量不是最低的，不更新，直接退出
        needMinBloodDp[row][col] = Math.max(1, remainBlood - nums[row][col]);//当前位置可以需要更少的血量，且需要继续往下更新
        //下一步：要么向上走,要么向左走
        recursive(nums, needMinBloodDp, row - 1, col, needMinBloodDp[row][col]);
        recursive(nums, needMinBloodDp, row, col - 1, needMinBloodDp[row][col]);
    }

    /**
     * 辅助分析结果的方法:打印二维数组
     */
    private static void printArray(String title, int[][] nums) {
        if (nums == null || nums.length == 0) return;
        int rows = nums.length;
        int cols = nums[0].length;
        System.out.println(title);
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                System.out.print(String.format("%2d;", nums[i][j]));
            }
            System.out.println();
        }
    }

    /***********************测试***************************/
    @Test
    public void test() {
        int[][] bloods1 = {{-2, -3, 3}, {-5, -10, 1}, {0, 30, -5}};//7
        int[][] bloods2 = {{-2, -5, 3}, {-5, -10, 1}, {0, 30, -5}};//8
        int[][] bloods3 = {{-2, -5, 3}, {-5, -10, 1}, {0, -30, -5}};
        int[][] bloods4 = {{2, 5, 3}, {5, -10, 1}, {0, 30, -5}};
        int[][] bloods = bloods4;
        printArray("原始的血量数组:", bloods);
        System.out.println("--------------动态规划方法---------------");
        System.out.println(String.format("需要的最少的血量：%3d", needMinBlood(bloods)));
        System.out.println("--------------递归方法---------------");
        System.out.println(String.format("需要的最少的血量：%3d", needMinBlood_DP(bloods)));
    }


    /*
         //根据scanner输入转化为二维数组
    public static int[][] sccanerInTobloods() {
        Scanner scanner = new Scanner(System.in);
        int rows = Integer.valueOf(scanner.nextLine());
        int cols = Integer.valueOf(scanner.nextLine());
        String line = scanner.nextLine();
        String[] numStrs = line.split(" ");
        int[][] nums = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                nums[i][j] = Integer.parseInt(numStrs[i * rows + j]);
            }
        }
        return nums;
    }

    //测试专用
    public static void main(String[] args) {
        //注释：在非main方法中调用Scanner.nextLine是无效的。
        int[][] bloods = sccanerInTobloods();
    }
    */
}