Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n. For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
题目分析：乍一看题目，比较天真的想法是：先从不大于n的最大的完全平方数开始组合，如果和超过了n，就换小一点的完全平方数。但问题是，最后如果凑不齐的话，只能添加很多1，总量上就不是最少的了。
从另一个角度来想，用穷举法来求解就是把不大于n的所有可能的完全平方数的组合都算出来，然后找出和为n的组合中数量最少的那种组合。如果不大于n的完全平方数有m个的话，这个方法的时间复杂度是O（m^m）。显然不可行。
如果我们能够记录已经找到的最小组合，那么稍大一些的数只需要在此基础上添加若干个完全平方数即可。这里面就包含了动态规划
/** * Created by Gracecoder on 2017/3/28. * 如果我们能够记录已经找到的最少组合，那么稍大一些数只需要在此基础上添加若干个完全平方数即可，这里面就包含了动态规划的思想。 * 定义一个dp数组，每个元素初始化为MAX_VALUE * dp[i]表示和为i的最少组合数 * j在i的基础上，依次加每个整数的平方，直到超过n * 动态转移方程： dp[i+j*j] = min(dp[i+j*j],dp[i]+1) */ public class leetcode279 { public int numSquares(int n) { int[] dp = new int[n+1]; for (int i = 0 ; i <= n ; i++) dp[i] = Integer.MAX_VALUE; dp[0] = 0; for (int i = 0 ; i <= n ; i++) for (int j = 1; i + j*j <= n ;j++) dp[i+j*j] = Math.min(dp[i+j*j],dp[i]+1); return dp[n]; } }