用C++完成编程：Description 给出一个N *N的正方形，其中每个数字不是0就是1 现在希望你找出一个面积最大的正方形，其中的数字全是1 Format Input 第一行给出数字N，代表正方形的大小。 下面若干行用来描述这个矩形. N<=1000 Output 输出你找出来的正方形的边长 Samples 输入数据 1 4 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 输出数据 1 2

分析：

这是一个经典的动态规划问题，可以用DP求解。我们可以定义一个二维数组 dp[i][j] 表示以 (i,j) 为右下角的最大正方形的边长。那么我们如何求解这个二维数组呢？我们可以根据 (i,j) 所在位置的上、左和左上三个位置的最小值，来更新 dp[i][j] 的值。即：

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

这个公式的意思是，以 (i,j) 为右下角的最大正方形的边长，要么是以 (i-1,j) 为右下角的最大正方形的边长加 1，要么是以 (i,j-1) 为右下角的最大正方形的边长加 1，要么是以 (i-1,j-1) 为右下角的最大正方形的边长加 1。我们需要取三个中的最小值。如果 (i,j) 位置的值为 0，那么 dp[i][j] 就是 0。

最后，我们遍历整个 dp 数组，找到 dp[i][j] 的最大值，即为所求的最大正方形的边长。

代码：