【动态规划】正方形计数

解题思路：
dp就完事，
状态表示：dp[ i ][ j ]表示的是以（i，j）为右下角的正方形有几个；
（同时也代表着最大正方形的边长是多少）
转移方程：
if（a[ i ][ j ]==0） dp[ i ][ j ]=0;
else dp[ i ][ j ]=min(dp[ i -1 ] [ j ],dp[ i ][ j -1 ],dp[ i -1 ][ j -1 ])+1;
用图片的方式可能更容易理解
蓝色代表 dp[ i -1 ][ j -1 ]
绿色代表 dp[ i -1 ] [ j ]
红色代表 dp[ i ][ j -1 ]
三者都要满足等于3，dp[ i ][ j ]才为4
否则还是形成不了边长为4的正方形

附上代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5005;
const double eps=1e-8;
const ll mod=1e9+7;
ll z,k,t,n,m,p,x,y,b,c,ans=0;
int a[maxn][maxn],dp[maxn][maxn];
char s[maxn][maxn];
int main(){
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>s[i][j];
if(s[i][j]=='0') a[i][j]=0;
else a[i][j]=1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i-1][j-1]==0) continue;
dp[i][j]=min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]))+1;
ans+=dp[i][j];
}
}
cout<<ans<<endl;
return 0;
}

最后

以上就是会撒娇麦片为你收集整理的【动态规划】正方形计数的全部内容，希望文章能够帮你解决【动态规划】正方形计数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。