Leetcode 221. Maximal Square (python+cpp)

题目

解析：动态规划

对于在矩阵内搜索正方形或长方形的题型，一种常见的做法是定义一个二维 dp 数组，其中 dp[i][j] 表示满足题目条件的、以 (i, j) 为右下角的正方形或者长方形的属性。对于本题，则表示 以(i,j)为右下角的全由1构成的最大正方形面积。如果当前位置是0，那么dp[i][j]即为0；如果 当前位置是1，我们假设dp[i][j]= k2，其充分条件为dp[i-1][j-1]、dp[i][j-1]和dp[i-1][j]的值必须 都不小于(k?1)2，否则(i,j)位置不可以构成一个边长为 k 的正方形。同理，如果这三个值中的 的最小值为 k?1，则(i,j)位置一定且最大可以构成一个边长为 k 的正方形。综上所述，状态转移方程为：dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]) + 1

这边dp的size可以是与matrix的形状相同，如果相同的话，那么第一行和第一列需要手动初始化；也可以比matrix的长宽各大1，那么这个时候多出来那一行设置全0就可以作为动态规划的初始化，两种方法的python代码分别如下：
python版本1:

class Solution:def maximalSquare(self, matrix: List[List[str]]) -> int:# 二维dp解法1if not len(matrix) or not len(matrix[0]):return 0m = len(matrix)n = len(matrix[0])dp = [[0]*n for _ in range(m)]ans = 0for i in range(m):for j in range(n):if i==0 and matrix[i][j]=='1':dp[i][j] = 1ans = max(ans,dp[i][j])elif j==0 and matrix[i][j]=='1':dp[i][j] = 1ans = max(ans,dp[i][j])else:if matrix[i][j]=='1':dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]) + 1ans = max(ans,dp[i][j])return ans*ans

python版本2：

class Solution:def maximalSquare(self, matrix: List[List[str]]) -> int:# 二维dp解法1if not len(matrix) or not len(matrix[0]):return 0m = len(matrix)n = len(matrix[0])dp = [[0]*(n+1) for _ in range(m+1)]ans = 0for i in range(1,m+1):for j in range(1,n+1):if matrix[i-1][j-1]=='1':dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]) + 1ans = max(ans,dp[i][j])return ans*ans

当然这道题目也可以进行状态压缩，压缩的方法和64 Minimum Path Sum的方法类似。只定义一维dp, dp[j-1]代表dp[i][j-1], 更新前dp[j]代表dp[i-1][j]。唯一不同的是这边需要一个临时变量来储存dp[i-1][j-1]。如果觉得这种压缩方法难以理解的话，大可不必纠结，无伤大雅
python代码如下：

class Solution:def maximalSquare(self, matrix: List[List[str]]) -> int:# 状态压缩一维dp解法if not len(matrix) or not len(matrix[0]):return 0m = len(matrix)n = len(matrix[0])dp = [0]*(n+1)ans = 0prev = 0for i in range(1,m+1):for j in range(1,n+1):temp = dp[j]if matrix[i-1][j-1]=='1':dp[j] = min(prev,dp[j-1],dp[j]) + 1ans = max(ans,dp[j])else:dp[j] = 0prev = tempreturn ans*ans

C++版本代码如下：
C++写法有两个注意点：

• 在C++里面，" "代表的是string，是不可以直接用’==‘比较的，但是’ '定义的char是可以直接比较的
• C++的min函数只接受两个参数

class Solution {
    
public:int maximalSquare(vector<vector<char>>& matrix) {
    if (matrix.empty() || matrix[0].empty()) return 0;int m = matrix.size();int n = matrix[0].size();int ans = 0;vector<vector<int>> dp(m+1,vector<int>(n+1,0));for (int i=1;i<=m;i++){
    for (int j=1;j<=n;j++){
    // 在C++里面，""代表的是string，是不可以直接用'=='比较的，但是''定义的char是可以的if (matrix[i-1][j-1]=='1'){
    // C++的min函数只接受两个参数dp[i][j] = min(min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1;ans = max(ans,dp[i][j]);}}} return ans*ans;}
};