DP12.md

DP12 骑士见公主

Solution 1

需要自底向上求解, 因为答案明显跟起点没有关系, 而距离终点越近答案越好求解.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int row = in.nextInt();
        int col = in.nextInt();

        int[][] hp = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                hp[i][j] = in.nextInt();
            }
        }

        int[][] dp = new int[row][col];

        dp[row - 1][col - 1] = Math.max(1, 1 - hp[row - 1][col - 1]);

        for (int i = row - 2; i >= 0; i--) {
            dp[i][col - 1] = Math.max(1, dp[i + 1][col - 1] - hp[i][col - 1]);
        }

        for (int i = col - 2; i >= 0; i--) {
            dp[row - 1][i] = Math.max(1, dp[row - 1][i + 1] - hp[row - 1][i]);
        }

        for (int i = row - 2; i >= 0; i--) {
            for (int j = col - 2; j >= 0; j--) {
                // 需要多少血才能通过这个地方.
                dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - hp[i][j]);
            }
        }

        System.out.println(dp[0][0]);
    }
}