iT邦幫忙

2

動態規劃經典題: 計算有幾個正方形

我們可能都看過這樣的益智題,
請問下圖中有幾個正方形呢?
(我可能畫的沒有很方正,就想像它是正的吧)

https://ithelp.ithome.com.tw/upload/images/20200521/20117114UNGBnZDdDJ.png

答案不是單純看到的十個,
因為還要考慮邊長>1的正方形,
本題有15個正方形:

  • 邊長 = 1 的有正方形有10個
  • 邊長 = 2 的有正方形有4個
  • 邊長 = 3 的有正方形有1個

在leetcode上面看到一題之後,
發現這類問題可以用程式來算啦~

參考題目: 1277. Count Square Submatrices with All Ones

題意: 給你一個由0和1組成的 m * n矩陣,計算有幾個正方形全由1組成
範例:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15

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

發現其實這一題跟之前有一題求最大正方形面積的題目很像,
定義令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 (如果格子(i,j)=0 就不會有正方形)

當我們建完這張表之後,把這張表格的數字加總,
即能夠得到正方形數量了,
因為DP[i][j]上的值即為以格子(i,j)為矩形右下角可以形成幾個正方形,
如圖示:
https://ithelp.ithome.com.tw/upload/images/20200521/20117114tIBi8htNhV.png

c++ 程式碼:

class Solution {
public:
    int countSquares(vector<vector<int>>& 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 sqaureNum = 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;
                    sqaureNum += DP[i][j];
                }
            }
        }
        return sqaureNum;
    }
};

看更多題目,返回主頁: 系列篇章統整: 好好規劃學習動態規劃(Dynamic Programming)


1 則留言

1
franchottse
iT邦新手 5 級 ‧ 2020-05-25 12:16:35

您好,我想問一下在for loop裡面,是不是應該是i<Rj<C?因為看來好像如果是i<=Rj<=C的話在讀取DP時應該有可能會是out of bound的。另外想問一下我可不可以這樣理解DP,DP[i][j]是在說包括這一格在內(DP[i][j]),可以形成多少個正方形。例如說DP[3][4]是在說這一格可以形成三個分別為邊長=1,邊長=2和邊長=3的正方形,就像以下這圖:
https://ithelp.ithome.com.tw/upload/images/20200525/20127399SGbkR904Lu.png

你好,我的DP表格大小是開(R+1)*(C+1)的,最左上角的座標記為(1,1)而非(0,0),所以不會out of bound(為了程式好寫)

另外,你理解的蠻好的,圖示很清楚,謝謝分享~
DP[i][j]就是以這一格為正方形的右下角可以形成幾個正方形

啊...你對。我看錯R和C的大小。感謝回答。

我要留言

立即登入留言