fangzhuan.cpp

n*n的方砖最小要几块边长小于n的方砖才能铺满,用动态规划的角度解决此问题

#include <stdio.h>
#define MAX_N 100  //n允许的最大值
int n;
int f[MAX_N+1][MAX_N+1]; //用来存储f(x,y)的值
int min( int a, int b ) //取两个数的较小值
{
 if( a < b ) 
  return a;
 else 
  return b;
}
int CalF( int x, int y ) //利用公式3计算f(x,y)
{
 int res, k;
 if( ( x ==y ) && ( x < n ) )  //直接有一个x=y正方形填充
  return 1;
 else {
  res = 100000;
  for( k = ( x / 2 ); k < x; k++ )  //通过k划分的划分依次查找
   res = min( res, f[k][y] + f[x-k][y] );
  return res;
 }
}
void work() 
{
 int x, y;
  for( x = 1; x <= n; x++ )   //从小到大的算出每一个f(i,j),其中1<=i<x;1<=j<y
  for( y = 1; y <= n; y++ ) 
{
   f[x][y] = CalF(x,y);    //递归调用最优填充
   f[y][x] = f[x][y];      //对称

 }    
}
 void main() 
{
 for( n = 2; n <= MAX_N; n++ )  //从n=2计算到n=MAX_N
{
  work();
  printf("%5d %5d\n",n,f[n][n]);
}
}