1、題目
最大正方形 - 力扣（LeetCode） https://leetcode-cn.com/problems/maximal-square/
2、題解
這道題目可以使用動態(tài)規(guī)劃的思想，也就是將原問題拆解成子問題，再分治的想法膊升。
在此題中掏秩，其實就是把計算在整個數(shù)組中最大的正方形的這個問題殷费，拆解成兩個小的問題追驴，一是儲存以該點為右下角的正方形的邊長大小，二是比較這個數(shù)組中儲存的值的大小恶复。這樣就可以得到最終的結果怜森。
解釋一下，為什么是以該點為右下角的正方形的邊長大小
當我們判斷以某個點為正方形右下角時最大的正方形時谤牡，那它的上方副硅，左方和左上方三個點也一定是某個正方形的右下角，否則該點為右下角的正方形最大就是它自己了翅萤。那具體的最大正方形邊長呢恐疲？我們知道，該點為右下角的正方形的最大邊長套么，最多比它的上方培己，左方和左上方為右下角的正方形的邊長多1，此時有兩種情況胚泌，一是它的上方省咨，左方和左上方為右下角的正方形的大小都一樣的，這樣加上該點（即上三點某一個正方形的邊長加1）就可以構成一個更大的正方形玷室。二它的上方零蓉，左方和左上方為右下角的正方形的大小不一樣，合起來就會缺了某個角落穷缤，這時候只能取那三個正方形中最小的正方形的邊長加1了敌蜂。
最后，分享一下了解動態(tài)規(guī)劃的文章津肛？
動態(tài)規(guī)劃算法入門章喉，這就夠了 https://baijiahao.baidu.com/s?id=1631319141857419948&wfr=spider&for=pc
3、代碼
//1、動態(tài)規(guī)劃
class Solution {
public int maximalSquare(char[][] matrix) {
//排除異常情況
if(matrix.length==0||matrix[0].length==0){
return 0;
}
int result=0;
int rows = matrix.length;
int columns = matrix[0].length;
int[][] dp = new int[rows][columns];//用dp來保存結果
for (int i = 0; i < rows; i++) {
if(matrix[i][0]=='1'){
dp[i][0]=1;
result=1;
}
}
for (int j = 0; j < columns; j++) {
if (matrix[0][j]=='1'){
dp[0][j]=1;
result=1;
}
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < columns; j++) {
if(matrix[i][j]=='1'){
dp[i][j] = getMin(dp[i][j - 1], dp[i - 1][j - 1], dp[i - 1][j])+1;
result=getMax(result,dp[i][j]);
}
}
}
return result*result;
}
//得到最小整數(shù)值
private int getMin(int... values){
int minValue = Integer.MAX_VALUE;
for (int value:values){
if(value<minValue){
minValue=value;
}
}
return minValue;
};
//得到最大整數(shù)值
private int getMax(int... values){
int maxValue = Integer.MIN_VALUE;
for (int value:values){
if(value>maxValue){
maxValue=value;
}
}
return maxValue;
}
}
4囊陡、執(zhí)行結果
image.png
