1.求路径总数

分析

代码实现：

public int uniquePaths (int m, int n) {
    // 创建矩阵
    int[][] pathNum = new int[m][n];
    // 初始化 F(i,0) 和 F(0,k);
    for (int i = 0; i < m; i++) {
        pathNum[i][0] = 1;
    }
    for (int k = 1; k < n; k++) {
        pathNum[0][k] = 1;
    }
    for (int row = 1; row < m; row++) {
        for (int col = 1; col < n; col++) {
            pathNum[row][col] = pathNum[row - 1][col] + pathNum[row][col - 1];
        }
    }
    return pathNum[m - 1][n - 1];
}

2.最小路径和

题目

分析

和上一个题类似

状态 F(i，k)： 表示从 (0，0) 到达 (i，k) 的最短路径和
状态转移方程：
F(i，k) ：min( F(i-1，k)，F(i，k-1) ) + array[ i ] [ k ]

第一行：
F(0，k)：F(0，k-1) + array[0] [ k ]
第一列：
F(i，0)：F(i-1，0) + array[ i ] [0]

初始状态： F(0，0) = array[0][0]
返回结果： F(row-1，col-1)

代码实现：

public int minPathSum(int[][] grid) {
    if(grid == null || grid.length == 0 || grid[0].length == 0){
        return 0;
    }
    int row = grid.length;
    int col = grid[0].length;
    // F(0,0), F(0,i), F(i,0)初始化
    for(int i = 1;i < row;i++) {
        grid[i][0] = grid[i - 1][0] + grid[i][0];
    }
    for(int k = 1;k < col;k++) {
        grid[0][k] = grid[0][k - 1] + grid[0][k];
    }
    for(int i = 1;i < row;i++) {
        for(int k = 1;k < col;k++) {
            grid[i][k] = Math.min(grid[i - 1][k],grid[i][k - 1]) + grid[i][k];
        }
    }
    return grid[row - 1][col - 1];
}