1 /* 2     题意：问n最少能是几个数的平方和 3     01背包：j*j的土地买不买的问题 4     详细解释：http://www.cnblogs.com/vongang/archive/2011/10/07/2200721.html 5 */ 6 #include 
     
       7 #include 
      
        8 #include 
       
         9 #include 
        
         10 using namespace std;11 12 const int MAXN = 6e4 + 10;13 const int INF = 0x3f3f3f3f;14 int dp[MAXN];15 16 int main(void)        //URAL 1073 Square Country17 {18     //freopen ("I.in", "r", stdin);19 20     int n;21     while (scanf ("%d", &n) == 1)22     {23         memset (dp, 0, sizeof (dp));24         for (int i=1; i<=n; ++i)25         {26             dp[i] = dp[i-1] + 1;27             for (int j=2; j<=sqrt (n*1.0); ++j)28             {29                 if (i >= j * j)    dp[i] = min (dp[i], dp[i-j*j] + 1);30                 else    break;31             }32         }33 34         printf ("%d\n", dp[n]);35     }36 37 38     return 0;39 }