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.
题目如上，实际上相当于一个常规的背包问题，关于背包问题可以看看这篇帖子 动态规划0—1背包问题，讲的很好（PS:这个帖子用的ppt的背景我就感觉像是我们学校了，真是巧了。。。。）.代码如下，下面都是有注释的：
1 class Solution { 2 public: 3 int numSquares(int n) { 4 vector<int> pSqr(n + 1, 0); 5 for (int i = 0; i < n + 1; ++i){ 6 pSqr[i] = i;//这里取i一定是最大值了，应为至少也可以全由1来组成，相当于背包问题里面的0 7 } 8 for (int i = 0; i < n + 1; ++i){ 9 for (int j = 2; j <= sqrt(i); ++j){//从2开始是有原因的，应为i= 1，2，3的时候就是pSqr的值，这里就不用算了 10 if (j * j == i){ pSqr[i] = 1; break; } 11 pSqr[i] = min(pSqr[i], 1 + pSqr[i - j * j]);//这一步是关键 12 } 13 } 14 return pSqr[n]; 15 } 16 };
这个博客上讲的很多也帮了我不少，mark一下。
LeetCode OJ：Perfect Squares（完美平方）
原文：http://www.cnblogs.com/-wang-cheng/p/4857402.html