题源：LeetCode

链接：https://leetcode-cn.com/problems/perfect-squares

 

 

 一道比较简单的动态规划：

 1 class Solution {
 2 public:
 3     int numSquares(int n) {
 4         vector<int> f(n + 1);
 5         for (int i = 1; i <= n; i++) {
 6             int minn = INT_MAX;
 7             for (int j = 1; j * j <= i; j++) {
 8                 minn = min(minn, f[i - j * j]);
 9             }
10             f[i] = minn + 1;
11         }
12         return f[n];
13     }
14 };