学好算法没有捷径，最好的捷径就是多刷题，并且跳出舒适区，每道题都要寻找最优解，也不能老是做那些你自己比较擅长的题，不定期更新Leetcode的题，每道题都会给出多种解法以及最优解。
题目描述
在一个由0和1组成的二维矩阵内，找到只包含1的最大正方形，并返回其面积。
示例
输入:10100101111111110010输出:4解法一：暴力法
在一个二维矩形中，如果我们要确定一个矩阵，我们只需要知道确定它的左上角和右下角就可以了，而正方形相当于边相等的矩阵。这道题暴力法还是比较好做，就是把矩阵中的每一个点，都充当左上角来遍历搜索一下。
例如我刚开始把（0，0）这个点当左上角，然后向右下角搜索
搜索的过程中，用一个变量来记录最大正方形的面积。接着用（0，1）作为左上角，不断着向右下角搜索
当然，（0，1）这个位置本身就是0，所以是没有搜索的必要的，我这里只是做个演示。最终的代码如下，代码中也有详细的介绍
publicintmaximalSquare(char[][]matrix){//如果矩阵长或宽少于1则直接返回0if(matrix.length<1||matrix[0].length<1)return0;introws=matrix.length;intcols=matrix[0].length;//记录最大边长intmax=0;for(inti=0;i<rows;i++){for(intj=0;j<cols;j++){//把（i，j）作为左上角向右下角搜索if(matrix[i][j]=='1'){//此时正方形的边长intsqlen=1;booleanflag=true;//记录是否遇到0的位置while(sqlen+i<rows&&sqlen+j<cols&&flag){for(intk=j;k<=sqlen+j;k++){if(matrix[i+sqlen][k]=='0'){flag=false;break;}}for(intk=i;k<=sqlen+i;k++){if(matrix[k][j+sqlen]=='0'){flag=false;break;}}if(flag)sqlen++;}if(max<sqlen){max=sqlen;}}}}returnmax*max;}时间复杂度：O((mn)^2)空间复杂度：O(1)解法二：动态规划
对于动态规划，大部分情况下我们都会定义一个二维数组dp，然后定义dp[i][j]的含义，接着推导dp[i][j]与dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]之间的关系。当然，也可以是推导dp[i][j]与dp[i+1][j]、dp[i][j+1]、dp[i+1][j+1]之间的关系，下面我们讲下用dp该怎么解这道题。
1、首先我们定义dp[i][j]含义为正方形以dp[i][j]作为右下角时的最大边长值。
2、接着我们来推导他们的关系
显然，对于任意一点dp[i][j]，由于该点是正方形的右下角，所以该点的右边，下边，右下边都不用考虑，关心的是左边，上边，和左上边，也就是我们要推导dp[i][j]与dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]之间的关系。他们有如下关系
dp[i][j]=min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1]）+1
这个关系其实也不算难推，毕竟不能有0存在，所以只能取交他们三个点的交集。你们可以画个图，可能就比较好理解了。
代码如下：
publicintmaximalSquare(char[][]matrix){//如果矩阵长或宽少于1则直接返回0if(matrix.length<1||matrix[0].length<1)return0;introws=matrix.length;intcols=matrix[0].length;int[][]dp=newint[rows+1][cols+1];intmax=0;for(inti=1;i<=rows;i++){for(intj=1;j<=cols;j++){if(matrix[i-1][j-1]=='1'){dp[i][j]=Math.min(Math.min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1;max=Math.max(max,dp[i][j]);}}}returnmax*max;}时间复杂度：O(n*m)空间复杂度：O(n*m)解法三：动态规划优化
用动态规划时，可以说80%都是用二维数组，但是80%也都可以优化成一维数组，这很容易理解，大家看这个公式
dp[i][j]=min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1]）+1
通过上面的公式我们可以知道，我们要算dp[i][j]的值时，只需要用到dp[i-1][j],dp[i][j-1],dp[i-1][j-1]三个值就可以了。也就是说，我们在算矩阵dp第i行的值时，只需要用第（i-1）行的值，至于（i-2）的值根本就不需要用到
所以我们只需要用一个一维数组就可以了，然后每次算出第i行的值，就马上用一维数组dp[0…n]把这行值保存起来，供计算i+1行时使用。
如下图
new_dp[i]相当于二维矩阵的dp[i][j]
dp[i]相当于dp[i-1][j]
dp[i-1]相当于dp[i-1][j]
pre相当于dp[i-1][j-1]。
然后用一维矩阵的话，我们每次计算出new_dp[i]后，就马上用new_dp[i]覆盖dp[i]的值，并且还要用一个变量pre来保存dp[i-1][j-1]的值。
好吧，估计你也给我绕晕了，如果不大理解，强烈建议画图模拟一下
最终代码如下
publicintmaximalSquare(char[][]matrix){if(matrix.length<1||matrix[0].length<1)return0;introws=matrix.length;intcols=matrix[0].length;int[]dp=newint[cols+1];intmax=0,prev=0;for(inti=1;i<=rows;i++){for(intj=1;j<=cols;j++){inttemp=dp[j];if(matrix[i-1][j-1]=='1'){dp[j]=Math.min(Math.min(dp[j-1],prev),dp[j])+1;max=Math.max(max,dp[j]);}else{dp[j]=0;}prev=temp;}}returnmax*max;}时间复杂度：O(n*m)空间复杂度：O(n)额外话
动态规划是一个比较难的算法思想，特别是对于初学者，遇到动态规划的题基本凉，我刚开始也被搞过，后来能看懂关于动态规划的答案，但是自己写不出，一气之下做了几十道动态规划的题，发现做来做去套路都差不多，于是总结出了自己的一个套路模板，从此80%的动态规划题都会做。所以呢，后面找个时间我得写一写我的经验，这个经验适合看得懂动态规划，但又不知道怎么下手的人，不过写这篇文章估计需要挺长时间，所以几时写还没确定，，，，大家也可以学我，直接做50道动态规划的题，准稳。
看完有收获？那么希望老铁别吝啬你的三连击哦
1、点赞，可以让更多的人看到这篇文章2、关注我的原创微信公众号『苦逼的码农』，第一时间阅读我的文章，主打算法。公众号后台回复『电子书』，还送你一份电子书大礼包哦。3、也欢迎关注我的博客哦。
作者简洁
作者：帅地，一位热爱、认真写作的小伙，目前维护原创公众号：『苦逼的码农』，以写了150多篇文章，专注于写算法、计算机基础知识等提升你内功的文章，期待你的关注。转载说明：务必注明来源（注明：来源于公众号：苦逼的码农，作者：帅地）
