Given a positive integer n, find the least number of perfect square numbers (for example,
1, 4, 9, 16, ...) which sum to n.
Example：
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
解釋下題目：
給定一個(gè)正整數(shù)，求出這個(gè)數(shù)能夠被分成多少個(gè)平方數(shù)加起來的和，求出最少平方數(shù)的個(gè)數(shù)
1. 動(dòng)態(tài)規(guī)劃
實(shí)際耗時(shí)：18ms
public int numSquares(int n) {
if (n < 1) {
//error input
return -1;
}
if (n == 1 || n == 2 || n == 3) {
return n;
}
if (n == 4) {
return 1;
}
//special situation is done
//for easy, dp[1] means the number of 1,not 2.
int[] dp = new int[n + 1];
dp[0] = 0; //very important
dp[1] = 1; //1 = 1
dp[2] = 2; //2 = 1+1
dp[3] = 3; //3 = 1+1+1
dp[4] = 1; //4 = 4
for (int i = 5; i <= n; i++) {
//any integer can use 1+1+1+1.....to compose
int min = i;
for (int j = 1; ; j++) {
if (j * j > i) {
break;
}
min = Math.min(min, dp[i - j * j] + 1);
}
dp[i] = min;
}
return dp[n];
}
踩過的坑：9
??一開始我想的是貪心算法，給定一個(gè)數(shù)，找到比它小的最大的平方數(shù)，然后剩下的那個(gè)繼續(xù)這么做，直到最后收斂到1，2，3，4這種小的數(shù)字上，然而事實(shí)上，12就是一個(gè)反例，比12最小的平方數(shù)是9，然后剩下3，顯然3和9不是最優(yōu)解，因?yàn)樗麄冃枰?個(gè)數(shù)字（1+1+1+9），而（4+4+4）只需要三個(gè)數(shù)字。后來就往DP上面靠，發(fā)現(xiàn)12可以通過1,4,9這三個(gè)數(shù)字加點(diǎn)什么得到，而1,4,9都是一個(gè)數(shù)字，不一定是最大的是最優(yōu)的（這道題只滿足局部最優(yōu)解）
