给你一个整数n返回和为n的完全平方数的最少数量。这道题第一眼看我也没找到思路后来我发现它本质上就是个找零钱问题。想象你有无限多个面值为 1、4、9、16、25... 的硬币要凑出 n 块钱问最少用几个硬币。只不过这里的硬币面值正好是完全平方数。一说到无限个硬币凑金额这不就是完全背包嘛。每种硬币可以无限次使用求凑出目标金额的最少硬币数。怎么算 dp[i] 呢看最后一个加了什么。凑出 i 的最后一步一定是加了一个平方数比如 k²。那加上这个平方数之前已经凑出了 i - k²。所以dp[i] dp[i - k²] 1但这只是其中一种可能。因为最后一步加 1、加 4、加 9、加 16... 都是可能的我们得把所有可能都试一遍取最小的那个。于是状态转移方程就是dp[i] min( dp[i - 1²] 1, dp[i - 2²] 1, dp[i - 3²] 1, ... )只要 k² 不超过 i所有平方数都要考虑。代码如下class Solution { public: int numSquares(int n) { vectorintdp(n1,INT_MAX); dp[0]0; for(int i1;in;i){ for(int j1;j*ji;j){ dp[i]min(dp[i],dp[i-j*j]1); } } return dp[n]; } };这道题的困难之处就是能不能看出来它是一道完全背包问题看出来之后这道题就迎刃而解了
（支持资料、图片参考_相关定制）_文章底部可以扫码)
