【LeetCode】Day64-最小路径和 & 最大正方形

64. 最小路径和【中等】

和昨天的题差不多…就是加了一项每个位置有值

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

时间复杂度： O ( m n ) O(mn) O(mn)

空间复杂度： O ( n ) O(n) O(n)，优化后的，原始为 O ( m n ) O(mn) O(mn)

221. 最大正方形【中等】

1. 状态定义：dp[i][j] 表示以 (i, j) 为右下角，且只包含 1 的正方形的边长最大值。
2. 状态转移方程：dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1，证明过程如下图
   
   

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

时间复杂度： O ( m n ) O(mn) O(mn)

空间复杂度： O ( m n ) O(mn) O(mn)，可优化为 O ( n ) O(n) O(n)