Description:
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
Example:
Given n = 12, return 3 because 12 = 4 + 4 + 4
Given n = 13, return 2 because 13 = 4 + 9
Link:
http://www.lintcode.com/en/problem/perfect-squares/
题目意思：
给出一个正整数n，求这个正整数最小可以由几个平方数相加而成。
解题方法：
使用dp来解题，创建一个size为n+1的数组来储存从1~n的每个数的题解（平方数则为1）。
状态转移方程为dp[n] = min(dp[i] + dp[n-i])
Tips:
for(int j = 1; j*j <= i/2; j++) result[i] = result[i] > result[j*j] + result[i-j*j] ? result[j*j] + result[i-j*j] : result[i];
将j换成了j*j，是可以跳过一些不是平方数的数字，如果不换的话Lintcode时间报错但是leetcode可以AC。
Time Complexity：
当把j换成了j*j后，时间复杂度为O(nlogn)，否则为O(n^2)。
空间复杂度为O(n)。
完整代码：
int numSquares(int n) { if(n < 1) return 0; vector<int> result(n+1, INT_MAX); for(int i = 1; i*i <= n; i++) result[i*i] = 1; for(int i = 2; i <= n; i++) { if(result[i] == INT_MAX) for(int j = 1; j*j <= i/2; j++) result[i] = result[i] > result[j*j] + result[i-j*j] ? result[j*j] + result[i-j*j] : result[i]; } return result[n]; }
