剑指 Offer II 098. 路径的数目 / 剑指 Offer II 099. 最小路径之和

剑指 Offer II 098. 路径的数目【中等题】

思路：【动态规划】

二阶dp数组：
dp[i][j]表示从左上角走到下标为(i,j)的位置所需要的路径数目。

边界条件：
dp[0][0]=1

i = 0时:
终点位于矩阵上边界，dp[i][j]的值仅取决于左侧点dp
即dp[0][j] = dp[0][j-1]

j = 0时:
终点位于矩阵左边界，dp[i][j]的值仅取决于上侧点dp
即dp[i][0] = dp[i-1][0]

其实左边界和上边界的点从左上角出发的话，仅有一种路径到达，
即dp[0][j] = 1，dp[i][0] = 1。

转移方程：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

代码：

class Solution {
    public int uniquePaths(int m, int n) {
        //动态规划
        //定义dp数组，表示走到(i,j)位置可选的路径数目
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && j > 0){
                    //转移方程
                    //走到(i,j)位置的路径数由走到它左侧和上侧的路径数共同决定
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }else {
                    //边界条件
//                    //1.左上角起点
//                    if (i == 0 && j == 0){
//                        dp[0][0] = 1;
//                    }else if (i == 0){//2.上边界
//                        dp[0][j] = dp[0][j-1];
//                    }else {//3.左边界
//                        dp[i][0] = dp[i-1][0];
//                    }
                    dp[i][j] = 1;
                }
            }
        }
        //(m-1,n-1)位置即为m×n网格的右下角，dp数组的路径数始终是从左上角开始出发计算的，因此dp[m-1][n-1]即为题目所求总路径数目
        return dp[m-1][n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

---

剑指 Offer II 099. 最小路径之和【中等题】

思路：【动态规划】

解题思路参照上题，将dp[i][j]的值定义为从矩阵左上角走到(i,j)位置的最小路径和即可。

代码：

class Solution {
    public int minPathSum(int[][] grid) {
        //动态规划
        //排除特殊输入
        if (grid == null || grid.length == 0 || grid[0].length == 0){
            return 0;
        }
        int m = grid.length,n = grid[0].length;
        //定义数组dp dp[i][j]表示从矩阵左上角走到(i,j)时的最小路径和
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && j > 0){
                    //转移方程
                    dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
                }else {
                    //边界条件
                    if (i == 0 && j == 0){
                        dp[0][0] = grid[0][0];
                    }else if (i == 0){
                        dp[0][j] = dp[0][j-1] + grid[0][j];
                    }else {
                        dp[i][0] = dp[i-1][0] + grid[i][0];
                    }
                }
            }
        }
        //dp[m-1][n-1]即为从矩阵左上角走到右下角的最小路径和
        return dp[m-1][n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31