搞定数正方形问题的动态规划策略解析
描述:
晓萌有一个N×N的的棋盘,中间有N*N个正方形的1×1的格子,他随机在棋盘上撒上一些棋子(假设全部正好落在各个格子里)。他希望知道,当前的棋盘上有多少个不包含棋子的,由至少四个1×1的格子组成的正方形(正方形之间可以有重叠的部分)。
输入第1行为棋盘的边长N,第2行-第N+1组成一个每行有N个数字的棋盘,其中数字0表示这个格子内有棋子,1表示这个格子内没有棋子。(2≤N≤250)
输出包括多行,每行包括两个用空格分隔的数字,分别表示可以找到的正方形的边长和这种边长的正方形的个数。
样例输入
6
101111
001111
111111
001111
101101
111001
样例输出
2 10 //2*2的正方形有10个
3 4 //3*3的正方形有4个
4 1 //4*4的正方形有1个
分析:
显然这是个动态规划,若用暴力搜索,会在大数组上超时,所以需要每次保存上次的状态
先来分析下2*2的正方形,如下图:
从上图可以看出,当在第s[i][j]数组上,且这个数组值为1(有棋子),那它会与之前地s[i-1][j-1]、s[i-1][j]、s[i][j-1]有关,若这3个任意一个都不满足(为0)的话,那么s[i][j]就只能是个1*1正方形
再来深入分析,3*3的正方形,如下图:
从上图可以看出,要想第s[i][j]数组上构成一个大于等于3*3的正方形,必须s[i-1][j-1]、s[i-1][j]、s[i][j-1]都至少是个2*2的正方形,比如上图(3,3), 不然就会像上图(2,2)那样
从这里我们可以看出s[i][j]非0情况下, 会等于 这3个数组(s[i-1][j-1]、s[i-1][j]、s[i][j-1])的最小值+1
最后再分析一个有0数组,就迎刃而解了:
同样地对于一个n*n正方形(n>=2),必定满足(n-1)*(n-1)正方形、(n-2)*(n-2)正方形 ... ...
代码如下:
#include<stdio.h>
int s[300][300]={0},tp[300]={0};
int main()
{
int i,j,n,min=0,m=1,cnt;
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%1d",&s[i][j]);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(s[i][j]!=0) //第s[i][j]数组上,且这个数组值为1(有棋子)
{
min=(s[i-1][j]>s[i-1][j-1])?s[i-1][j-1]:s[i-1][j];
min=(s[i][j-1]>min)?min:s[i][j-1];
s[i][j]=min+1; //等于 这3个数组(s[i-1][j-1]、s[i-1][j]、s[i][j-1])的最小值+1
for(cnt=2;cnt<=min+1;cnt++) //对于一个n*n正方形(n>=2),必定满足(n-1)*(n-1)正方形、(n-2)*(n-2)正方形 ... ...
tp[cnt]++;
}
}
for(i=2;i<=n;i++)
if(tp[i]!=0)
{
if(m)
{
printf("%d %d",i,tp[i]);
m=0;
}
else
printf("\n%d %d",i,tp[i]);
}
return 0;
}
推荐阅读
-
搞定数正方形问题的动态规划策略解析
-
超级全面解析:矩阵连乘问题的动态规划解法(附C++代码及备忘录技巧)
-
搞定矩阵连乘问题的动态规划策略
-
搞定矩阵连乘问题的动态规划策略
-
算法简介:动态规划(DP)的概述及常见面试问题解析
-
深入解析C语言动态规划中的多种背包问题
-
动态规划算法的两种经典解决方式:最优子结构和DP数组的使用解析-动态规划算法问题 什么叫作最优子结构? 和动态规划有什么关系? 为什么动态规划遍历DP数组的方式有正着遍历,有倒着遍历,有斜着遍历? 最优子结构 最优子结构是某些问题的一种特定的性质,并不是动态规划问题所特有的. 很多问题都具有最优子结构,但是其中大部分不具有重叠子问题,所以不会归为动态规划系列的问题 最优子结构: 可以从子问题的最优结果推导出更大规模问题的最优结果 子问题之间必须相互独立 通过改造问题来优化由于子问题之间不独立而导致的最优子结构失效的情况: 问题: 假设学校有10个班,已知每个班的最高分与最低分差值的最大分数差,需要计算全校学生中的最大分数差 分析: 这样的问题就无法通过这10个班的最大分数差来推导出来,因为这10个班的最大分数差不一定就包含全校学生的最大分数差.比如全校的最大分数差可能是由8班的最高分和6班的最低分的分数差而得.这样就导致子问题之间不是互相独立的 改造问题: 直接进行问题改造 int result = 0; for (Student a : school) { for (Student b : school) { if (a is b) { continue; } result = max(result, |a.score - b.score|) } } return result; 改造问题就是将问题等价转化: 最大分数差就等价于最高分数与最低分数的差 那么就是要求最高和最低分数 求最高分数是具备最优子结构的,求最低分数也是具有最优子结构的 这样就样一个不具备最优子结构的问题转化为具备最优子结构的子问题 借助最优子结构解决最值问题,再解决最大分数差问题 题目: 求一棵二叉树的最大值,假设节点中的值都为非负数 int maxVal(TreeNode root) { if (root == null) { return -1; } int left = maxVal(root.left); int right = maxVal(root.right); return max(root.val, left, right); }
-
【算法•日更•第三十期】解析洛谷P4170 [CQOI2007] 涂色问题的区间动态规划策略