給一個(gè)正整數(shù) n, 找到若干個(gè)完全平方數(shù)(比如1, 4, 9, ... )使得他們的和等于 n姜凄。你需要讓平方數(shù)的個(gè)數(shù)最少。
樣例
給出 n = 12, 返回 3 因?yàn)?12 = 4 + 4 + 4顷蟀。
給出 n = 13, 返回 2 因?yàn)?13 = 4 + 9绞呈。
代碼
- DP
public class Solution {
/**
* @param n a positive integer
* @return an integer
*/
public int numSquares(int n) {
// dp[i]代表當(dāng)前元素i可以分解成的最少平方數(shù)個(gè)數(shù)
// 從0到n串稀，n + 1個(gè)數(shù)
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
// 比如9可以分解成3 * 3
for (int i = 0; i * i <= n; ++i) {
dp[i * i] = 1;
}
// i 的上一個(gè)接龍為去掉某個(gè)平方數(shù)j * j(j可多種取值)后剩余的i - j * j
// dp[i]的值依賴于dp[i - j * j]的值
for (int i = 0; i <= n; ++i) {
// j 如果從0開始會(huì)出現(xiàn) i - j * j 還是 i 無變化
// 無窮次計(jì)算后奇唤，不能直接分解成x * x 的dp[i] 的值為Integer.MAX_VALUE;
for (int j = 1; j * j <= i; ++j) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
}
- 另一種DP
public class Solution {
/**
* @param n a positive integer
* @return an integer
*/
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
for (int i = 0; i * i <= n; ++i) {
dp[i * i] = 1;
}
// dp[i] 可以確定dp[i + j * j]的值
for (int i = 0; i <= n; ++i) {
for (int j = 0; i + j * j <= n; ++j) {
dp[i + j * j] = Math.min(dp[i] + 1, dp[i + j * j]);
}
}
return dp[n];
}
}
兩種DP的區(qū)別是第一種計(jì)算當(dāng)前dp[i]的值要不斷向前計(jì)算摊滔，通過前面的dp數(shù)值來確定當(dāng)前dp[i]的值苔巨，第二種dp的做法是通過當(dāng)前dp[i]值確定后邊dp[i]的值
- Math
public class Solution {
/**
* @param n a positive integer
* @return an integer
*/
public int numSquares(int n) {
while (n % 4 == 0)
n /= 4;
if (n % 8 == 7)
return 4;
for (int i = 0; i * i <= n; ++i) {
int j = (int)Math.sqrt(n * 1.0 - i * i);
if (i * i + j * j == n) {
int res = 0;
if (i > 0)
res += 1;
if (j > 0)
res += 1;
return res;
}
}
return 3;
}
}
四平方和定理瞻润，看不懂
http://blog.csdn.net/jmspan/article/details/51148344
- BFS
public class Solution {
/*
* @param n: a positive integer
* @return: An integer
*/
public int numSquares(int n) {
if (n == 0) {
return 1;
}
int root = (int) Math.sqrt(n);
int[] roots = new int[root];
for (int i = 0; i < root; i++) {
roots[i] = (i + 1) * (i + 1);
}
int len = 0;
Queue<Integer> q = new LinkedList<>();
Set<Integer> set = new HashSet<>();
for (int r : roots) {
q.offer(r);
set.add(r);
}
while (!q.isEmpty()) {
len++;
int size = q.size();
for (int i = 0; i < size; i++) {
int curr = q.poll();
if (curr == n) {
return len;
}
for (int j = 0; j < roots.length; j++) {
int temp = curr + roots[j];
if (temp > n || set.contains(temp)) {
continue;
}
q.offer(temp);
set.add(temp);
}
}
}
return -1;
}
}
把所有小于平方n的數(shù)當(dāng)做結(jié)點(diǎn)喘垂，用BFS尋找最短路徑
