题解 | #最大正方形#

解题思路：
根据DP解题的三步骤
1.确定dp[][]数组的含义
此题的dp[i][j]，代表以坐标为(i,j)的元素为右下角的正方形的边长。
2.状态转移方程
dp[i][j]的值取决于dp[i-1][j],dp[i-1][j-1],dp[i][j-1]的最小值
即左方正方形的边长，左上方正方形的边长，上方正方形的边长三者的最小值。
3.边界
由于状态转移方程中涉及i-1，j-1，所以i和j一定要大于0.
故dp[0][] 和 dp[][0]要首先确定。
#=============================================================================================
'''

#
# 最大正方形
# @param matrix char字符型二维数组 
# @return int整型
#
class Solution:
    def solve(self , matrix ):
        # write code here
        m = matrix
        #for i in m:
        #    print('m=',i)

        r = len(m)
        c = len(m[0])
        dp = [[0]*c for _ in range(r)]
        maxLen = 0
        for i in range(r):
            for j in range(c):
                if (i==0 or j==0) and m[i][j]==1:
                    dp[i][j] = 1
                elif m[i][j]==1:
                    dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
                if dp[i][j]>maxLen:
                    maxLen = dp[i][j]
        #for i in dp:
        #    print('dp=',i)
        #print('maxLen=',maxLen)
        return maxLen*maxLen

# 此题牛客原题中输入的是“字符型”二维数组，这里是“数字型”

m = [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]   # 4
s = Solution()
print(s.solve(m))