62. 不同路径

• DP状态：dp[i][j]表示i*n的不同路径数；
• DP转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1];

public int uniquePaths(int m, int n) {
    // 边界+1便于判断
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i < m + 1; i++) {
        for (int j = 1; j < n + 1; j++) {
            if (i == 1 && j == 1) {
                // 起点初始值为1
                dp[i][j] = 1;
            } else {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }
    return dp[m][n];
}

63. 不同路径 II

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int rows = obstacleGrid.length, cols = obstacleGrid[0].length;
    int[][] dp = new int[rows + 1][cols + 1];
    for (int i = 1; i < rows + 1; i++) {
        for (int j = 1; j < cols + 1; j++) {
            if (obstacleGrid[i - 1][j - 1] == 1) {
                // 障碍物不可到达
                dp[i][j] = 0;
            } else if (i == 1 && j == 1) {
                // 起点初始值为1
                dp[i][j] = 1;
            } else {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }
    return dp[rows][cols];
}

64. 最小路径和

public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int min = 0;
            // 注意边界条件
            if (i == 0) {
                min = dp[i + 1][j];
            } else if (j == 0) {
                min = dp[i][j + 1];
            } else {
                min = Math.min(dp[i][j + 1], dp[i + 1][j]);
            }
            dp[i + 1][j + 1] = min + grid[i][j];
        }
    }
    return dp[m][n];
}

剑指 Offer 13. 机器人的运动范围

public int movingCount(int m, int n, int k) {
    int res = 0;
    // 定义DP状态
    boolean[][] visit = new boolean[m + 1][n + 1];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 判断当前坐标是否合法
            if (getNum(i) + getNum(j) <= k) {
                // 如果左上可达
                if (visit[i][j + 1] || visit[i + 1][j]
                        // 或者当前是起点
                        || (i == 0 && j == 0)) {
                    // 则当前坐标可达
                    visit[i + 1][j + 1] = true;
                    res++;
                }
            }
        }
    }
    return res;
}

// 计算各位相加和
private int getNum(int n) {
    int res = 0;
    while (n != 0) {
        res += (n % 10);
        n /= 10;
    }
    return res;
}

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

public int maxValue(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    int[][] dp = new int[rows + 1][cols + 1];
    for (int i = 1; i < rows + 1; i++) {
        for (int j = 1; j < cols + 1; j++) {
            // 取上左最大值，加上当前值
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
        }
    }
    return dp[rows][cols];
}