思路：dp，转移方程 dp[i] = min(dp[i-1] + 1, dp[i - j*j] + 1)；这个转移方程很好理解，类似0-1背包，买j*j的这块地还是不买。跟很像。

ps：上午wa了好几次，下午昨晚福州的网赛又拿过来这个题，不知道改了哪地方，没积分钟就ac了。看来是老天可怜我网赛被虐。。。T_T

My Code:

#include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; const int N = 60005; int dp[N]; int main(){
   //freopen("data.in", "r", stdin); int n, i, j; while(cin >> n){
           memset(dp, 0, sizeof(dp)); for(i = 1; i <= n; i++){
               dp[i] = dp[i-1]+1; for(j = 1; j <= (int)sqrt((double)n); j++){
   if(i >= j*j){
                       dp[i] = min(dp[i], dp[i - j*j] + 1);                 }             }         }         cout << dp[n] << endl;     } return 0; }