本文共 978 字，大约阅读时间需要 3 分钟。

分析：

       这个题暴力解也能过了，最佳解法使用动态规划的思想：本题考虑的是正方形的面积，所以算出最长的边长就好。我们假设dp[i][j] 是以 [i][j] 为顶点的最大的正方形边长。我们可以写出状态转移方程：

若 [i][j] 这个点是1 ：那么dp[i][j]=min{dp[i-1][j-1]，dp[i-1][j]，dp[i][j-1]}+1。

否则 : dp[i][j]=0

暴力解法：

       遍历矩阵每个元素，以这个元素作为正方形的左上角，寻找最大面积。复杂度为O(n*n）。这种算法存在大量的重复计算比如： 左上角[0][0]元素计算是有必要的，但是[1][1]元素计算就重复了。因为[1][1]元素所形成的正方形矩阵是[0][0]元素的子集。所以我们在动态规划思想里面假设dp[i][j] 是以 [i][j] 为顶点的最大的正方形边长。

import java.util.Scanner;/** * @author: Mr.Hu * @create: 2019-03-13 21:10 */public class Main{    public static void main(String[] args) {        Scanner sc =new Scanner(System.in);        while (sc.hasNextInt()){            int n=sc.nextInt();            char[][] a =new char[n][];            for (int i = 0; i < n; i++) {       //输入变为二维整形数组                a[i] =sc.next().toCharArray();            }            int[][] dp =new int[n][a[0].length];  //dp 存以a[i][j]结尾最长的边长  注意输入数据不一定是正方形            int max=0;            for (int i = 0; i < n; i++) {           //将字符数组变为整形数组                for (int j = 0; j 

转载地址：https://blog.csdn.net/h2453532874/article/details/88542850 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！