【动态规划】【路径问题】不同路径和礼物的最大价值

1. 不同路径 Ⅰ

62. 不同路径

image.png|474

算法原理

1. 确定状态表示
   • dp[i][j] 表示：走到 [i, j] 位置的时候，一共有多少种方式
2. 状态转移方程
   • 根据最近的一步，划分问题
   • 到达 [i, j] 位置之前的一小步，有两种情况
     1. 从 [i-1, j] 的位置向下走一步，到达 [i, j]
     2. 从 [i, j-1] 的位置向右走一步，到达 [i, j]

• 此时我们要求一共有多少种方法，因此状态方程为：dp[i][j] = dp[i-1][j] + dp[i][j-1]

1. 初始化

• 根据状态转移方程，需要知道左边和上面的值才能确定要求的值。最左边和最上面会发生越界的情况
  • 将最左边和最上面的值都填好
  • 增加虚拟节点（左边加一列，上面加一行）

image.png|424

• 增加虚拟节点
  1. 虚拟节点里面的值，要保证后面填表的结果都是正确的
     • 红色的数字是原本走到这里的路径数
     • 按绿色的值来初始化就能保证红色路径数量符合
  2. 下标的映射

1. 填表顺序
   • 从状态方程来看，顺序就是从下往上填每一行；在填每一行的时候从左往右
2. 返回值
   • 返回 dp[m][n]

代码编写

public int uniquePaths(int m, int n) {  
    //1. 创建 dp 表  
    int[][] dp = new int[m+1][n+1];  
  
    //2. 初始化  
    dp[0][1] = 1;  
  
    //3. 填表  
    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];  
}

2. 不同路径 Ⅱ

63. 不同路径II

image.png

算法原理

1. 确定状态表示
   • dp[i][j] 表示：到达 [i, j] 位置的时候，一共有多少种方法
2. 状态转移方程

• dp[i][j]
  • 有障碍物==> 0
  • 无障碍物==> dp[i][j] = dp[i-1][j] + dp[i][j-1]
    • 即使前一步有障碍物也无妨，因为有障碍物的地方 dp=0

1. 初始化

里面的值，要保证后面的填表是正确的

image.png|339

• 只要红星格子是正确的，那后面推的时候都是正确的（周围的 0 是不产生影响的）
• 第一个格子的意义是：机器人刚开始站在这个位置，有多少种方法
• 所以只要红星左边或者上面为 1，其他都为 0 就行了

下标的映射关系

• 之前的 (0, 0) 跑到了 (1, 1) 位置，（2, 3） 跑到了 （3, 4） 位置。加入虚拟格子之后，整体向右下移动了
• 所以想从 dp 表找回之前矩阵的位置，那么下标就得统一 -1 才可以

1. 填表顺序
   • 大方向从上往下
   • 每一行从左往右
2. 返回值
   • 返回 dp[m][n]

代码编写

public int uniquePathsWithObstacles(int[][] ob) {  
    //1. 创建 dp 表  
    int m = ob.length;  
    int n = ob[0].length;  
    int[][] dp = new int[m+1][n+1];  
  
    //2. 初始化  
    dp[1][0] = 1;  
  
    //3. 填表  
    for (int i = 1; i <= m; i++) {  
        for (int j = 1; j <= n; j++) {  
            if(ob[i-1][j-1] == 0) {  
                dp[i][j] = dp[i-1][j] +dp[i][j-1];  
            }  
        }  
    }  
    return dp[m][n];  
}

• 注意二维数组分行和列长度的方法
• dp 表在创建的时候，里面的值本来就是 0，所以我们只需要看一下没有障碍物时候的情况
  • 判断有没有障碍物，只需要看原来的 ob 二维数组的值是 0 还是 1 即可

时间复杂度：m*n（两个 for 循环） 空间复杂度：m*n（弄了个二维 dp 表）

3 . 礼物的最大价值

剑指 offer 47. 礼物的最大价值

image.png

算法原理

1. 确定状态表示
   • dp[i][j] 表示：走到 [i, j] 位置时，此时的最大价值
2. 状态转移方程

• dp[i][j]
  • 从 [i-1, j] 走过来==> dp[i-1][j] + g[i][j]
  • 从 [i, j-1] 走过来==> dp[i][j-1] + g[i][j]
  • dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + g[i][j]

1. 初始化

里面的值，要保证后面的填表是正确的

image.png|451

• 因为每个格子都是选左和上的最大值，都设 0 就可以了

下标的映射

• 多加了一行一列，整体向右下移动了一个单位长度
• 所以之后若想找到原始坐标的值，只需要横纵坐标均 -1 即可

1. 填表顺序
   • 大方向从上往下
   • 每一行从左往右
2. 返回值
   • 返回 dp[m][n]

代码编写

public int jewelleryValue(int[][] frame) {  
    //1. 创建 dp 表  
    int m = frame.length;  
    int n = frame[0].length;  
    int[][] dp = new int[m+1][n+1];  
  
    //2. 初始化  
    //3. 填表  
    for (int i = 1; i <= m; i++)  
        for (int j = 1; j <= n; j++)  
            dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) + frame[i-1][j-1];  
    return dp[m][n];  
}

• 求本格价值的时候记得横纵坐标得 -1，返回到原来的位置

时间复杂度：m*n（两个 for 循环） 空间复杂度：m*n（弄了个二维 dp 表）