【算法 & 动态规划 &路径问题】二维dp问题

二维dp问题

• 解题思路
• 不同路径（medium）
• 地下城游戏（hard）

解题思路

状态表示常用思路

• dp[i][j] 表示从起始点(如 0,0) 到 i,j 位置满足题目要求的值
  • 填表顺序就是从左到右, 从上到下
• dp[i][j] 表示从点 i,j 到 指定位置 满足题目要求的值
  • 填表顺序就是从右到左, 从下到上

不同路径（medium）

题目链接

解题思路: 动态规划

1. 状态表示: dp[i][j] 表示从 0,0 到 i,j 最多可以有多少条路径
2. 状态转移方程
   • 依据机器人可以向下走或者向右走来分析状态转移方程
   • 向下走: 说明 (i,j) 可以由 (i-1,j) 位置过来 => dp[i][j] = dp[i-1][j]
   • 向右走: 说明 (i,j) 可以由 (i,j – 1) 位置过来 => dp[i][j] = dp[i][j – 1]
   • 综上所述: dp[i][j] = dp[i-1] [j] + dp[i][j-1]
3. 初始化
   • 依据状态转移方程以及取值范围, 行和列都多开辟一维
   • 为了保证填表的准确性: dp[0][1] = 1
4. 填表顺序: 从左到右, 从上到下
5. 返回值: dp[m][n]

代码:

class Solution {
    public int uniquePaths(int m, int n) {
        // dp[i][j] 表示从 1,1 到 i,j 一共有多少种走法
        // dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;
        for(int i = 1; i <= m; ++i) {
            for(int j = 1; j <= n; ++j) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
}

地下城游戏（hard）

题目链接

解题思路: 动态规划

1. 状态表示

   • 这道题如果定义成: 从起点开始, 到达 [i,j] 位置的时候, 所需的最低初始健康点数, 那么我们分析状态转移的时候会有一个问题: 就是当前的健康点数还会受到后续路径的影响。也就是从上往下的状态转移不能很好的解决问题.
   • 换另一个角度: 从[i,j] 位置出发, 到达终点时需要的最低初始健康点数.

2. 状态转移

   • 对于dp[i][j], 从[i,j] 位置出发, 下一步会有两种选择:
     • 走到右边然后走向终点
       • 那么我们在 [i,j] 位置的最低健康点数加上这一个位置的消耗, 应该要大于等于右边位置的最低健康点数, 也就是: dp[i][j] + dungeon[i][j] >= dp[i][j+1].
       • 取dp[i][j] 的最小值, 则 dp[i][j] = dp[i][j+1] – dungeon[i][j];
     • 走到下边, 然后走向终点
       • 那么我们在 [i,j] 位置的最低健康点数加上这一个位置的消耗, 应该要大于等于下边位置的最低健康点数, 也就是: dp[i][j] + dungeon[i][j] >= dp[i+1][j].
       • 取dp[i][j] 的最小值, 则 dp[i][j] = dp[i+1][j] – dungeon[i][j];
   • 综上所述, 我们需要的是两种情况下的最小值, 因此可得状态转移方程为: dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) – dungeon[i][j]
   • 但是,如果当前位置的 dungeon[i][j] 是一个比较大的正数的话, dp[i][j] 的值可能变成 0 或者负数, 也就是最低点数小于 1, 那么骑士就会死亡.但是骑士只要有一点血量到该点, 就可以吃到该位置的恢复, 从而恢复血量, 也就可以继续往前走. 因此我们求出来的 dp[i][j] 如果小于等于 0 的话, 说明此时的最低初始值应该为 1, 则 dp[i][j] = max(1,dp[i][j])

3. 初始化

   • 在 dp 表最后⾯添加⼀⾏，并且添加⼀列后，所有的值都先初始化为⽆穷⼤，然后让dp[m][n – 1] = dp[m – 1][n] = 1 即可。

4. 填表顺序: 从下往上, 从右往左

5. 返回值: dp[0][0]

代码

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        // dp[i][j] 表示从 i,j 位置到 右下角 最低需要的血量
        int m = dungeon.length, n = dungeon[0].length;
        int[][] dp = new int[m+1][n+1];

        for(int i = 0; i <= m; ++i) {
            dp[i][n] = Integer.MAX_VALUE;
        }

        for(int j = 0; j <= n; ++j) {
            dp[m][j] = Integer.MAX_VALUE;
        }

        dp[m][n-1] = dp[m - 1][n] = 1;

        for(int i = m - 1; i >= 0; --i) {
            for(int j = n - 1; j >= 0; --j) {
                dp[i][j] = Math.min(dp[i][j + 1],dp[i + 1][j]) - dungeon[i][j];
                dp[i][j] = Math.max(1,dp[i][j]);
            }
        }
        return dp[0][0];
    }
}