动态规划问题——骑士救公主

题目：

给定一个二维数组map，含义是一张地图，如：

-2       -3        3

-5       -10      1

0        30       -5

骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。如果数字数负数，则骑士损失对应血量，如果是正数，骑士恢复对应血量，在任何位置骑士的血量都不能少于1，为了保证骑士能见到公主，初始血量至少是多少？根据map，返回初始血量。

思路：

 定义和地图大小一样的矩阵 dp，dp[i][j] 的含义是如果骑士要走上位置（i，j），并且从该位置选一条最优的路径，最后走到右下角，骑士起码应该具备的血量。最终要的是dp[0][0]的结果。

代码实现：

    public static int minHP(int[][] map) {if (map == null || map.length == 0 || map[0] == null || map[0].length == 0) {return 1;}//初始化矩阵 dpint row = map.length;int col = map[0].length;int[][] dp = new int[row--][col--];//初始化dp矩阵右下角的值 如果这个位置是正数，有一滴血就可以，如果是负数，需要 绝对值+1dp[row][col] = map[row][col] > 0 ? 1 : -map[row][col] + 1;//初始化最下面一行 该位置值是 他右边值减去map中该位置的值，结果不能为负for (int j = col - 1; j >= 0; j--) {dp[row][j] = Math.max(dp[row][j+1] - map[row][j], 1);}int right = 0;int down = 0;for (int i = row -1; i >=0; i--) {//初始化最后一列dp[i][col] = Math.max(dp[i+1][col] - map[i][col], 1);//填其他位置for (int j = col - 1; j >= 0; j--) {right = Math.max(dp[i][j+1] - map[i][j], 1);down = Math.max(dp[i+1][j] - map[i][j], 1);dp[i][j] = Math.min(right, down);}}return dp[0][0];}

测试结果：