【題目描述】
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.
在一個二維01矩陣中找到全為1的最大正方形。
【題目鏈接】
www.lintcode.com/en/problem/maximal-square/
【題目解析】
考慮以f[i][j]為右下角頂點(diǎn)可以拓展的正方形邊長西设，那么可以由f[i-1][j]喉酌，f[i][j-1]，f[i-1][j-1]三者的最小值決定f[i][j]的最長邊長。
當(dāng)我們判斷以某個點(diǎn)為正方形右下角時最大的正方形時炭晒，那它的上方伙菜，左方和左上方三個點(diǎn)也一定是某個正方形的右下角，否則該點(diǎn)為右下角的正方形最大就是它自己了转唉。這是定性的判斷皮钠，那具體的最大正方形邊長呢？我們知道赠法，該點(diǎn)為右下角的正方形的最大邊長麦轰，最多比它的上方，左方和左上方為右下角的正方形的邊長多1砖织，最好的情況是是它的上方款侵，左方和左上方為右下角的正方形的大小都一樣的，這樣加上該點(diǎn)就可以構(gòu)成一個更大的正方形侧纯。但如果它的上方新锈，左方和左上方為右下角的正方形的大小不一樣，合起來就會缺了某個角落眶熬，這時候只能取那三個正方形中最小的正方形的邊長加1了妹笆。假設(shè)dp[i][j]表示以i,j為右下角的正方形的最大邊長，則有
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
當(dāng)然娜氏，如果這個點(diǎn)在原矩陣中本身就是0的話拳缠，那dpi肯定就是0了。
【參考答案】
