力扣动态规划基础版（矩阵型）

时间：2024-11-05 17:00:39

62.不同路径（唯一路径问题）

62. 不同路径https://leetcode.cn/problems/unique-paths/

方法一：动态规划 

 找状态转移方程，也就是说它从左上角走到右下角，只能往右或者往下走，那么设置一个位置为（i,j）它只能从（i-1，j）或者（i，j-1）走过来那么它的状态转移方程就是除了这个还要去思考边界条件，如果i=0那么就不满足右侧的状态转移方程，同理j

= 0也不行，就是边上的那些数，可以考虑到边上的那些数都可以设置为1，也就是f（i，0）和f（0，j）都是1

class Solution {
    public int uniquePaths(int m, int n) {
    int[][] f = new int [m][n];
    for(int i = 0; i < m; i ++){
        f[i][0] = 1;
    }
    for(int j = 0; j < n ; j++){
        f[0][j] = 1;
    }
    for(int i = 1; i < m; ++i){
        for(int j = 1; j < n; ++j){
            f[i][j] = f[i -1][j]  + f[i][j -1];
        }
    }
    return f[m - 1][n - 1];
    }
}

优化空间复杂度：

这个唯一路径问题可以进行空间复杂度的优化 ：由于 f(i,j) 仅与第 i 行和第 i−1 行的状态有关，因此我们可以使用滚动数组代替代码中的二维数组，使空间复杂度降低为 O(n)。

这个思路是。我们不需要存储每一个点，只需要存储它的上面一个点就行，再加上上一列的值即可，从第二行开始，每一行进行遍历只需要原始的值加上上一列的值。边界条件就是第一行都是1（很好想）

class Solution {
    public int uniquePaths(int m, int n) {
        //对于每一行，按列进行遍历
        //第一行先都设为1
        int f[] = new int[n];
        for(int i = 0; i < n; ++i){
            f[i] = 1;
        }
        //从第二行开始，对每一列进行遍历，它的f值只和它的前一列相关
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                f[j]  += f[j - 1];//这个f[j]再每一次行遍历都更新，它就代表着上一次遍历的上一行的内容 
            }
        }
        return f[n - 1];
    }
}

方法二：排列组合

因为它只能向下走或者是向右走，所以就只有

从左上角到右下角的过程中，我们需要移动 m+n−2 次，其中有 m−1 次向下移动，n−1 次向右移动。因此路径的总数，就等于从 m+n−2 次移动中选择 m−1 次向下移动的方案数。实现这个排列组合的式子就行，其实实现这个技巧也是有讲究的，因为上面等于下面两个的和，所以位数是一样的，做一个循环，每一项相乘就行

class Solution {
    public int uniquePaths(int m, int n) {
        long ans = 1;
        for(int x =  n,y = 1; y < m; ++x,++y){
            ans = ans *x/y;
        }
        return (int)ans;
    }
}

64.最小路径和 

64. 最小路径和https://leetcode.cn/problems/minimum-path-sum/还不错这道题自己写出来了，感觉就是前面那个题目的变式，状态转移方程就是第（i，j）个点的最小值由于只能向下或者向右，所以最小值就是它上面的或者左边的加上它自身的值。然后边界条件考虑（0，0），再考虑第一行和第一列。

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int dp[][] = new int [m][n];
        dp[0][0] = grid[0][0];
        for(int i = 1 ; i < m ;++i){
            dp[i][0] = dp[i -1][0] + grid[i][0];
        }
        for(int j = 1; j < n;++j){
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j] = grid[i][j] + Math.min(dp[i -1][j],dp[i][j - 1]);
            }
        }
        return dp[m -1][n -1];
    }
}

63.不同路径Ⅱ

63. 不同路径 IIhttps://leetcode.cn/problems/unique-paths-ii/

这个其实大同小异，但是加了个障碍也就是说带障碍的要做个判断，如果他这是0，这条路就死了直接置为0

然后这次构建dp数组是多了一个空间确实好用 

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int dp[][] = new int [m+1][n+1];
        dp[1][1] = 1;
        for(int i = 1; i < m + 1; ++i){
            for(int j = 1;j < n + 1; ++j){
                if(obstacleGrid[i -1][j -1] == 1){
                    dp[i][j] = 0;
                }
                else{
                    dp[i][j] = Math.max(dp[i][j],dp[i - 1][j]+dp[i][j -1]);//这里的max是为了dp[1][1]
                }
            }
        }
        return dp[m][n];
    }
}

做完了这个题我又回头看第62题，确实是这样创建数组更舒服，我就又写了一版62的题解

class Solution {
    public int uniquePaths(int m, int n) {
    int[][] f = new int [m + 1][n + 1];
    f[1][1] = 1;
    for(int i = 1; i < m + 1; ++i){
        for(int j = 1; j < n + 1; ++j){
            f[i][j] = Math.max(f[i -1][j]  + f[i][j -1],f[i][j]);
        }
    }
    return f[m][n];
    }
}

对于63题我觉得不能用这钟方式，因为如果这样设置他的转移方程是求最小值，这样的话边界是0的情况下都算进去了，就错误了。

120.三角形最小路径和

方法一：动态规划 

120. 三角形最小路径和https://leetcode.cn/problems/triangle/看到这个题目有点恍惚了，感觉是和以前的题目没啥区别，状态转移方程也是很好想，就是这一个的最小值就是上面和上面的左边的最小值加上这个值的min，但是三角形边界的情况还是特殊一点，因为就是比如在第i行的第0个发现j-1到达不了，以及在第i行的第i个发现在第i-1行的第i列也到达不了，所以要考虑这个两边的边界情况。其他的部分还是很像的，还需注意的是triangle是数组想取值用get

 for(int i = 1; i < m; ++i){
            dp[i][0] = dp[i -1][0] + triangle.get(i).get(0);
            for(int j =1;j < i; ++j){
                dp[i][j] = Math.min(dp[i -1][j -1],dp[i -1][j]) +triangle.get(i).get(j);
            }
            dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
        }

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        int [][] dp = new int [m][m];
        dp[0][0] = triangle.get(0).get(0);
        for(int i = 1; i < m; ++i){
            dp[i][0] = dp[i -1][0] + triangle.get(i).get(0);
            for(int j =1;j < i; ++j){
                dp[i][j] = Math.min(dp[i -1][j -1],dp[i -1][j]) +triangle.get(i).get(j);
            }
            dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
        }
        int minTol = dp[m -1][0];
        for(int i = 1; i < m; i++){
            minTol = Math.min(minTol,dp[m -1][i]);
        }
        return minTol;
    }
}

931.下降路径最小和

931. 下降路径最小和https://leetcode.cn/problems/minimum-falling-path-sum/这道题目其实和上一道的思路属于是殊途同归的，需要考虑这些形状的边界的情况，与三角形不同，这个要考虑左右两边，容易出错的点就是在考虑右边的时候注意下标m -1同时考虑最后一排的最小值。做过上面那道题，这道题可以轻松ac

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int dp[][]  = new int [m][m];
        //初始化
        for(int i = 0; i < m; ++i){
            dp[0][i] = matrix[0][i];
        }
        for(int i = 1; i < m; ++i){
            dp[i][0] = matrix[i][0] + Math.min(dp[i - 1][0],dp[i -1][1]); 
            for(int j = 1; j < m - 1; ++j){
                dp[i][j] = matrix[i][j] + Math.min(Math.min(dp[i -1][j -1],dp[i -1][j]),dp[i -1][j + 1]);
            }
            dp[i][m - 1] = matrix[i][m -1] + Math.min(dp[i -1][m -1],dp[i -1][m -2]);
        }
        int minres = dp[m -1][0];
        for(int i = 0; i < m; ++i){
             minres = Math.min(minres,dp[m -1][i]);
        }
        return minres;
    }
}

221.最大正方形 

221. 最大正方形https://leetcode.cn/problems/maximal-square/

方法一：暴力

暴力来说的话还是比较好想的，就是先遍历一遍，如果有1就设置为res为1了，然后就找到这个左上角，去算一下潜在的最大正方形，再去遍历去找，先沿着对角线如果是1的话，就再看看其他地方是否满足，设置flag，如果不满足置为false

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;int n = matrix[0].length;
        int res = 0;
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return res;
        }
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(matrix[i][j] == '1'){
                    res = Math.max(1,res);
                    //计算可能的最大的正方形边长
                    int currentMaxside = Math.min(m - i,n - j);
                    for(int k = 1 ;k < currentMaxside; ++k){
                       //判断新增的一列是否都是1
                       boolean flag = true; 
                       if(matrix[i + k][j + k] == '0'){
                        break;
                       }
                       for(int q = 0; q < k; ++q){
                        if(matrix[i + k][j + q] == '0' || matrix[i + q][j + k] == '0'){
                            flag = false;
                            break;
                        }
                       }
                        if(flag){
                            res = Math.max(res,k + 1);
                        }
                        else{
                            break;
                        }
                    }
                }
            }
        }
        int ress = res * res;
        return ress;
    }
}

方法二：动态规划

这个就有点秒了，考虑的是用 dp(i,j) 表示以 (i,j) 为右下角，且只包含 1 的正方形的边长最大值。

如果该位置的值是 1，则 dp(i,j) 的值由其上方、左方和左上方的三个相邻位置的 dp 值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 1。

这样的话状态转移方程就可以用下面式子来表示

然后注意边界条件就是，如果在第一排或者第一列，瑞国他是1的话，dp[i][j]只能为1 

dp[i][j] = Math.min(Math.min(dp[i -1][j],dp[i - 1][j -1 ]),dp[i][j -1]) + 1
class Solution {
    public int maximalSquare(char[][] matrix) {
        int Maxres = 0;
        int rows = matrix.length;
        int columns = matrix[0].length;
        int [][] dp = new int [rows][columns];
        for(int i = 0; i < rows; ++i){
            for(int j = 0; j < columns; ++j){
                if(matrix[i][j] == '1'){
                    if(i == 0 || j == 0){
                        dp[i][j] = 1;
                    }
                    else{
                        dp[i][j] = Math.min(Math.min(dp[i -1][j],dp[i - 1][j -1 ]),dp[i][j -1]) + 1;
                    }
                Maxres = Math.max(Maxres,dp[i][j]);
                }
            }
        }
        int Maxsquare = Maxres * Maxres;
        return Maxsquare;
    }
}

相关文章