重磅乾貨，第一時間送達
作者：葉 虎
Maximal Square是道非常有意思的演算法題。它是一個典型的動態規劃問題，同時也是2017京東面試題，2016華為機考題。
1
題目描述：
有一個n*m大小的矩陣，其元素值為0或者1，求這個矩陣中全有1組成的最大方塊其大小。
2
輸入描述
每個輸入包含一個測試用例。每個測試用例的第一行包含兩個整數n（2
3
輸出描述
輸出矩陣中全有1組成的最大方塊其大小。
4
輸入例子
4 6
1 1 0 1 1 1
0 1 1 1 1 1
1 1 0 1 1 1
1 1 0 0 1 1
5
輸出例子
3
思路分析：
本題為一個典型的動態規劃問題，因此可以使用動態規劃的思想進行。動態規劃重要的一個特點是要複用子問題。
假設以matrix［i］［j］為右下頂點的最大方塊的大小為dp［i］［j］。那麼dp［i］［j］的計算否可以複用比其更小的子問題呢？不難想象，如果matrix［i］［j］=0，那麼dp［i］［j］=0。當matrix［i］［j］=1時，此時要考察dp［i-1］［j-1］，dp［i-1］［j］及dp［i］［j-1］，這是由於以matrix［i］［j］的為右下頂點的最大方塊由上面三個位置決定，而且是木桶效應，由最小值所決定，即dp［i］［j］=min + 1。考慮到邊界條件，可以得到最終的遞迴方程為：
只需要找到最大的dp［i］［j］值即得到最大方塊的大小。整個演算法的時間複雜度與空間複雜度均為O（n*m）。
具體實現程式碼(C++)
（點開大圖，可詳細清晰地看程式碼）
本文只是Maximal Square演算法題其中的一種解法，在此拋磚引玉。歡迎留言或加群討論。
好訊息，小白學視覺團隊的知識星球開通啦，為了感謝大家的支援與厚愛，團隊決定將價值149元的知識星球現時免費加入。各位小夥伴們要抓住機會哦！
下載1：OpenCV-Contrib擴充套件模組中文版教程
下載2：Python視覺實戰專案52講
下載3：OpenCV實戰專案20講
交流群
