[leetcode]动态规划之Maximal Square

心已赠人 2021-09-29 01:40 366阅读 0赞

### 动态规划之Maximal Square ###

*  题目
 *  思考
 *  代码

# 题目 #

[leetcode入口][leetcode]

# 思考 #

之前认为dp表格的含义是到dp\[i\]\[j\]是到表格中(i,j)这个点为止，最优的解  
但是通过这道题，dp\[i\]\[j\]可以有了新的含义  
**新的含义**:  
dp\[i\]\[j\]：以包含点(i,j)的最优解，最后只需找出表格中的最优解即可了。

**这道题的解题思路**：  
除了第一行和第一列外，dp\[i\]\[j\]代表以(i,j)为右下顶点的最大正方形的边长  
状态转移方程：  
dp\[i\]\[j\]=min(dp\[i-1\]\[j-1\],min(dp\[i-1\]\[j\],dp\[i\]\[j-1\]))

刚开始思维受限于如何判断正方形，后来看了题解发现只要判断(i,j)临近的三个位置的解再+1即可

# 代码 #

class Solution { 
    public:
        int maximalSquare(vector<vector<char>>& matrix) { 
            if(matrix.size()==0) return 0;
            //初始化dp数组，dp中存的是以dp[i][j]为右下角的最大正方形的边长
            vector<vector<int>> dp(matrix.size(),vector<int>(matrix[0].size(),0));
            
            //边长
            int length=0;
            
            //初始化第一行和第一列
            for(int i=0;i<matrix[0].size();i++){ 
                dp[0][i]=matrix[0][i]-48;
                if(matrix[0][i]=='1'){ 
                    length=1;
                }
            }
            
            for(int i=0;i<matrix.size();i++){ 
                dp[i][0]=matrix[i][0]-48;
                if(matrix[i][0]=='1'){ 
                    length=1;
                }
            }
            
            for(int i=1;i<matrix.size();i++){ 
                for(int j=1;j<matrix[i].size();j++){ 
                    //如果该点是1
                    if(matrix[i][j]=='1'){ 
                        if(matrix[i][j-1]=='1'&& matrix[i-1][j]=='1'&&matrix[i-1][j-1]=='1'){ 
                            dp[i][j]=min(dp[i][j-1],min(dp[i-1][j-1],dp[i-1][j]))+1;
                            length=max(length,dp[i][j]);
                        }
                        else{ 
                            dp[i][j]=1;
                        }
                        
                    }
                    else{ 
                        dp[i][j]=0;
                    }
                }
            }
            
            return length*length;
            
        }
    };

[leetcode]: https://leetcode.com/problems/maximal-square/