每日一题：地下城游戏 （dp）

题意

给定权值矩阵，需要从左上角走到右下角，只能往右或往下走且权值会累加，问至少需要提前准备多少权值才能保证过程中不出现权值被耗尽的情况。

Solution

正着不太好写，可以尝试倒过来dp，$dp[i][j]$ 表示当前位置到终点至少需要准备多少权值，这样每个点要么从下边转移，要么从右边转移，选择最小的那个点转移即可，过程中需要保证权值至少为1，得到转移方程：$dp[i][j] = max(min(dp[i+1][j],dp[i][j+1])-mp[i][j],1)$。

Code

class Solution {
    public int calculateMinimumHP(int[][] mp) {
        int n = mp.length, m = mp[0].length;
        int[][] dp = new int[n + 1][m + 1];
        for(int i = n; i >= 0; i--) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[n][m - 1] = dp[n - 1][m] = 1;
        for(int i = n - 1; i >= 0; i--) {
            for(int j = m - 1; j >= 0; j--) {
                dp[i][j] = Math.max(Math.min(dp[i + 1][j], dp[i][j + 1]) - mp[i][j], 1);
            }
        }
        return dp[0][0];
    }
}