动态规划之矩阵路径类

leetcode 62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

示例 1:输入: m = 3, n = 2 输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:输入: m = 7, n = 3 输出: 28

如果申请一个二维空间的dp[][],那么状态转移方程为dp[i][j] = dp[i - 1][j]+dp[i][j - 1];

public int uniquePaths1(int m, int n) {
        if (m <= 0 || n <= 0) {
            return 0;
        }
        if (m == 1 || n == 1) {
            return 1;
        }
        int[][] dp = new int[m][n];

        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 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 - 1][n - 1];

    }

    //空间压缩
    public int uniquePaths(int m, int n) {
        if (m <= 0 || n <= 0) {
            return 0;
        }
        if (m == 1 || n == 1) {
            return 1;
        }
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] = dp[j] + dp[j - 1];

            }
        }
        return dp[n - 1];
    }

leetcode 63. 不同路径 II

 /**
     * 空间压缩
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0) {
            return 0;
        }
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1 || obstacleGrid[row - 1][col - 1] == 1) {
            return 0;
        }
        int[] dp = new int[col];
        dp[0] = 1;
        for (int i = 1; i < col; i++) {
            if (dp[i - 1] == 0 || obstacleGrid[0][i] == 1) {
                dp[i] = 0;
            } else {
                dp[i] = 1;
            }
        }

        for (int i = 1; i < row; i++) {
            if (dp[0] == 1 && obstacleGrid[i][0] == 0) {
                dp[0] = 1;
            }else {
                dp[0] = 0;
            }

            for (int j = 1; j < col; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                } else {
                    dp[j] = dp[j - 1] + dp[j];
                }
            }

        }
        return dp[col - 1];
    }


    public int uniquePathsWithObstacles1(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0) {
            return 0;
        }
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1 || obstacleGrid[row - 1][col - 1] == 1) {
            return 0;
        }
        int[][] dp = new int[row][col];
        dp[0][0] = 1;
        for (int i = 1; i < row; i++) {
            if (dp[i - 1][0] == 0 || obstacleGrid[i][0] == 1) {
                dp[i][0] = 0;
            } else {
                dp[i][0] = 1;
            }
        }

        for (int i = 1; i < col; i++) {
            if (dp[0][i - 1] == 0 || obstacleGrid[0][i] == 1) {
                dp[0][i] = 0;
            } else {
                dp[0][i] = 1;
            }
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }

        }
        return dp[row - 1][col - 1];
    }

leetcode 64. 最小路径和

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;
        int[][] dp = new int[row][col];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < row; i++) {
            dp[i][0] = grid[i][0] + dp[i - 1][0];
        }

        for (int i = 1; i < col; i++) {
            dp[0][i] = grid[0][i] + dp[0][i - 1];
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {

                dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[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;
        int[] dp = new int[col];
        //初始化第一行
        dp[0] = grid[0][0];
        for (int i = 1; i < col; i++) {
            dp[i] = dp[i - 1] + grid[0][i];
        }
        for (int i = 1; i < row; i++) {
            dp[0] = grid[i][0] + dp[0];
            for (int j = 1; j < col; j++) {
                dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]);
            }
        }
        return dp[col - 1];
    }

动态规划，说白了就是用缓存来记录一些重复子问题，避免重复计算，是一种用空间换时间的操作。

最长递增子路径

public class LongestIncreasingPath329 {
 
    public static void main(String[] args) {
        int[][] matrix = {
                {9, 9, 4},
                {6, 6, 8},
                {2, 1, 1}
        };
        int max = new LongestIncreasingPath329().longestIncreasingPath(matrix);
        System.out.println(max);
    }
    int[][] d = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    //先来看看暴力解法
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length == 0){
            return 0;
        }

        int max = Integer.MIN_VALUE;
        int row = matrix.length;
        int col = matrix[0].length;
        int path = 0;
        //从每个位置出发都尝试一遍
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                path = path(matrix, i, j);
                max = max > path ? max : path;

            }

        }
        return max;
    }

    private int path(int[][] matrix, int row, int col) {
        int num = 0;
        for (int i = 0; i < 4; i++) {
            int newRow = row + d[i][0];
            int newCol = col + d[i][1];
            if (newRow >= 0 && newCol >= 0 && newRow < matrix.length && newCol < matrix[0].length && matrix[row][col] > matrix[newRow][newCol]) {
                num = num > (path(matrix, newRow, newCol)) ? num : (path(matrix, newRow, newCol));
            }
        }

        return ++num;
    }

    //从中可以看出，在计算中进行了大量的重复计算，因此。可以想办法将重叠子问题记录下来，避免重复计算。
    //引入一个二元数组dp[][]，用来记录从某个点出发的最长路径，也就是动态规划解法。



    public int longestIncreasingPathdp(int[][] matrix) {
        if(matrix == null || matrix.length == 0){
            return 0;
        }

        int max = -1;
        int row = matrix.length;
        int col = matrix[0].length;
        int path = 0;
        int[][] dp = new int[row][col];
        //从每个位置出发都尝试一遍
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                path = path(matrix, i, j,dp);
                max = max > path ? max : path;

            }

        }
        return max;
    }

    private int path(int[][] matrix, int row, int col,int[][] dp) {
        if(dp[row][col]!=0){
            return dp[row][col];
        }
        for (int i = 0; i < 4; i++) {
            int newRow = row + d[i][0];
            int newCol = col + d[i][1];
            if (newRow >= 0 && newCol >= 0 && newRow < matrix.length && newCol < matrix[0].length && matrix[row][col] > matrix[newRow][newCol]) {
                dp[row][col] = dp[row][col] > (path(matrix, newRow, newCol,dp)) ? dp[row][col] : (path(matrix, newRow, newCol,dp));
            }
        }
        return ++dp[row][col];
    }

}