Use dp[I] to represent the minimum number of perfect squares that make up I. If there is a j, 1<=j and jj <= I, consider updating dp[I] with dp[i-j * j] if j squared is one of the perfect squares that make up I. That is, dp[I] = min(dp[I], dp[i-j * j] + 1); The solution for the least perfect squares that make up I is the solution for the least perfect squares that make up I -jj plus j squared. I recurses from small to large from 1 to n, constantly updating the value of dp[I], and finally returning dp[n] is the answer.
The code is as follows:
class Solution { public: int numSquares(int n) {! [](https://p9-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/6875d3b6130249088803a7ec71e27bef~tplv-k3u1fbpfcp-zoom-1.image)! [](https://p1-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/5925a14a1abf479480f94b4c98fdd9d7~tplv-k3u1fbpfcp-zoom-1.image) vector<int> dp(n + 1, INT_MAX); dp[0] = 0; for(int i = 1; i <= n; ++i) { for(int j = 1; j * j <= i; ++j) { dp[i] = min(dp[i], dp[i - j * j] + 1); } } return dp[n]; }};Copy the code