动态规划-最大的正方形面积

朴灿烈づ我的快乐病毒、 2024-04-18 23:46 72阅读 0赞

## 题目表述 ##

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0  
1 0 1 1 1  
1 1 1 1 1  
1 0 0 1 0

Return 4.

## 思路 ##

使用动态规划来求解，算法时间复杂度O(n^2)。

dp\[i\]\[j\] ： 以(i, j)为右下角的面积最大的正方形的边长。

初始条件：最上面一行，最左边一列，可以直接得到dp值。

更新公式：matrix\[i\]\[j\] == ‘0’ - > dp\[i\]\[j\] = 0

matrix\[i\]\[j\] == ‘1’ - > dp\[i\]\[j\] = min(dp\[i - 1\]\[j\], dp\[i - 1\]\[j - 1\], dp\[i\]\[j - 1\]) + 1

## 代码 ##

#include<iostream>
    #include<vector>
    const int _MAX = 10;
    
    using namespace std;
    
    char matrix[_MAX][_MAX];
    int dp[_MAX][_MAX];
    
    int min3(int a, int b, int c){
        
        a = a < b ? a : b;
        return a < c ? a : c;
    }
    
    int main(){
        
        int n, m;
        cin>>n>>m;
        for(int i = 0; i < n; i++){
        
            for(int j = 0; j < m; j++){
        
                cin>>matrix[i][j];
            }
        }
    
        
        int res = 0;
        for(int i = 0; i < n; i++){
        
            for(int j = 0; j < m; j++){
        
                if(matrix[i][j] == 1)dp[i][j] = 1;
                else dp[i][j] = 0;
            }
        }
    
        for(int i = 1; i < n; i++){
        
            for(int j = 1; j < m; j++){
        
                if(matrix[i][j] == '1'){
        
                    dp[i][j] = min3(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
                    res = res > dp[i][j] ? res : dp[i][j];
                }
            }
        }
        cout<<res * res<<endl;
        return 0;
    }
    
    /* 
    4 5
    1 0 1 0 0 
    1 0 1 1 1 
    1 1 1 1 1 
    1 0 0 1 0 
     */

[omegaxyz.com]: http://www.omegaxyz.com