iT邦幫忙

2

動態規劃經典題: 最大正方形面積

參考題目: LeetCode- 221. Maximal Square
題目敘述: 給定一個矩陣,只包含0和1,請找出最大的正方形面積只包括1
例子:

Input: 

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

Output: 4

想法: 令DP[i][j] 表示以格子(i,j)為矩形右下角所能形成的最大矩形邊長,觀察當格子(i,j)為1時,DP[i][j] = min(DP[i][j - 1], DP[i - 1][j], DP[i - 1][j - 1]) + 1

程式碼(c++):

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.empty())
            return 0;
        int R = matrix.size(), C = matrix[0].size();
        vector<vector<int>> DP = vector(R+1, vector<int>(C+1, 0));
        int maxSqLen = 0;
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                if (matrix[i-1][j-1] == '1'){
                    DP[i][j] = min(min(DP[i][j - 1], DP[i - 1][j]), DP[i - 1][j - 1]) + 1;
                    maxSqLen = max(maxSqLen, DP[i][j]);
                }
            }
        }
        return maxSqLen * maxSqLen;
    }
};

尚未有邦友留言

立即登入留言