Perfect Squares解題報告
1212 ワード
Description:
Gven a positive integer n、find the least number of perfect square numbers（for example、1、4、9、16、…）which sum to n.
Example:
Given=12、return 3 because 12=4+4+4 Given=13、return 2 because 13=4+9
Link:
http://www.lintcode.com/en/problem/perfect-squares/
タイトルの意味：
正の整数nを指定します。この正の整数が最小であれば、いくつかの平方数で加算されます。
問題の解き方：
dpを使って問題を解いて、1〜nの各数の問題解（平方数は1）を格納するために、sizeがn＋1の配列を作成します。状態遷移方程式は
Tips:
Time Coplexity：
完全コード:
Gven a positive integer n、find the least number of perfect square numbers（for example、1、4、9、16、…）which sum to n.
Example:
Given=12、return 3 because 12=4+4+4 Given=13、return 2 because 13=4+9
Link:
http://www.lintcode.com/en/problem/perfect-squares/
タイトルの意味：
正の整数nを指定します。この正の整数が最小であれば、いくつかの平方数で加算されます。
問題の解き方：
dpを使って問題を解いて、1〜nの各数の問題解（平方数は1）を格納するために、sizeが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に両替し、いくつかの平方数ではない数字をスキップしてもいいです。もし換えないなら、Litcodeの時間が間違っていますが、leetcodeはACできます。Time Coplexity：
jをj*jに変換すると、時間複雑度はO（nlogn）であり、そうでなければO（n^2）である。空間複雑度はO（n）である。完全コード:
int numSquares(int n) { if(n < 1) return 0; vector 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]; }