题目：

给你一个矩阵，其边长均为整数。你想把矩阵切割成总数最少的正方形，其边长也为整数。切割工作由一台切割机器完成，它能沿平行于矩形任一边的方向，从一边开始一直切割到另一边。对得到的矩形再分别进行切割。

输入数据：

输入文件中包含两个正整数，代表矩形的边长，每边长均在1—100之间。

输出数据：

输出文件包含一行，显示出你的程序得到的最理想的正方形数目。

输入输出示例：

CUTS.IN：

5 6

CUTS.OUT:

5

这道题呢可以用DFS+记忆化搜索，因为正在学习DP，所以就用DP写了

所以就用一个数组f[i][j]表示边长为i，j的矩形可以分出最少的正方形

所以就可知if(i==j)  f[i][j]=1;      所以就可以知道状态转移方程为：f[i][j]=min{f[i][k1]+f[i][j-k1],f[k2][j]+f[i-k2][j]}

(这里面f[i][k1]+f[i][j-k1]表示将矩形横着切开以后分成的两块包含的最少的矩形，同理可得f[k2][j]+f[i-k2][j]是竖着切开后两块的最少矩形) 1<=k1<j; 1<=k2<i;

 

代码如下：

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int f[2100][2100];int a[2100][2100];int main(){    int n,m;    cin>>n>>m;    memset(f,10,sizeof(f));    f[0][0]=0;    memset(a,0,sizeof(a));    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)        {            a[i][j]=1;            if(i==j)                f[i][j]=1;        }    for(int i=1;i<=n;i++)    {        for(int j=1;j<=m;j++)        {            /*if(i==j)                f[i][j]=1;*/            int k1,k2;            for(int k=1;k