一、題目
1、題目描述
給定正整數(shù) n，找到若干個完全平方數(shù)（比如 1, 4, 9, 16, ...）使得它們的和等于 n。你需要讓組成和的完全平方數(shù)的個數(shù)最少。
2、示例
示例1：
輸入: n = 12
輸出: 3
解釋: 12 = 4 + 4 + 4.
示例2：
輸入: n = 13
輸出: 2
解釋: 13 = 4 + 9.
二、解題思路
1、思路一
動態(tài)規(guī)劃
動態(tài)規(guī)劃算法與分治法類似,其基本思想也是將待求解問題分解成若干個子問題,先求解子問題,然后從這些子問題的解得到原問題的解。
而這個題求正整數(shù)n，我們可以運用動態(tài)規(guī)劃的思想，從1開始，求出直到n的個數(shù)最少的完全平方和。
首先聲明一個n+1大小的數(shù)組dp，那么dp[i]就代表數(shù)字i所需的最少完全平方數(shù)個數(shù)，dp[i]初值設為i，即最差情況就是i個1相加。
聲明變量j，j * j就代表平方數(shù)，如果dp[i-j * j]+1的個數(shù)比dp[i]小，那么dp[i]就設為dp[i-j * j]+1，這里+1的原因是j * j本身也要算一個數(shù)。
執(zhí)行用時 :30 ms, 在所有 java 提交中擊敗了76.91%的用戶
內(nèi)存消耗 :35.3 MB, 在所有 java 提交中擊敗了42.14%的用戶
2、思路二
BFS廣度優(yōu)先搜索
當每一次都可以判斷出多種情況，有多次的時候就適合用BFS-廣度優(yōu)先遍歷
使用BFS應注意：
隊列：用來存儲每一輪遍歷得到的節(jié)點；
標記：對于遍歷過的節(jié)點，應該將它標記，防止重復遍歷。
我們將它第一個平方數(shù)可能出現(xiàn)的情況做分析 只要 i * i < n 就行
再在此基礎上進行二次可能出現(xiàn)的平方數(shù)分析
注意：為了節(jié)省遍歷的時間，曾經(jīng)（ n - 以前出現(xiàn)的平方數(shù)） 這個值出現(xiàn)過，則在此出現(xiàn)這樣的數(shù)時直接忽略。
執(zhí)行用時 :15 ms, 在所有 java 提交中擊敗了93.46%的用戶
內(nèi)存消耗 :36.3 MB, 在所有 java 提交中擊敗了39.43%的用戶
3、一個有意思的思路
看到評論里這個思路的時候，默默感嘆吃了沒文化的虧，評論里給出了一個數(shù)學定理，沒仔細研究，有興趣可以看看
四平方定理： 任何一個正整數(shù)都可以表示成不超過四個整數(shù)的平方之和。 推論：滿足四數(shù)平方和定理的數(shù)n（四個整數(shù)的情況），必定滿足 n=4^a(8b+7)
執(zhí)行用時 :8 ms, 在所有 python 提交中擊敗了100.00%的用戶
內(nèi)存消耗 :11.7 MB, 在所有 python 提交中擊敗了44.68%的用戶
三、代碼
1、思路一代碼
class Solution {
public int numSquares(int n) {
int[] dp=new int[n+1];
dp[0]=0;
for(int i=1;i<=n;i++){
dp[i]=i;
for(int j=1;j*j<=i;j++){
if((dp[i-j*j]+1)<dp[i]){
dp[i]=dp[i-j*j]+1;
}
}
}
return dp[n];
}
}
2、思路二代碼
public class NumSquares {
private class Node {
int val;
int step;
public Node(int val, int step) {
this.val = val;
this.step = step;
}
}
public int numSquares(int n) {
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(n, 1));
boolean record[] = new boolean[n];
while (!queue.isEmpty()) {
int val = queue.peek().val;
int step = queue.peek().step;
queue.remove();
// 每一層的廣度遍歷
for (int i = 1;; i++) {
int nextVal = val - i * i;
// 說明已到最大平方數(shù)
if (nextVal < 0)
break;
// 由于是廣度遍歷，所以當遍歷到0時，肯定是最短路徑
if(nextVal == 0)
return step;
// 當再次出現(xiàn)時沒有必要加入，因為在該節(jié)點的路徑長度肯定不小于第一次出現(xiàn)的路徑長
if(!record[nextVal]){
queue.add(new Node(nextVal,step + 1));
record[nextVal] = true;
}
}
}
return -1;
}
}
3、思路三代碼
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
while n % 4 == 0:
n /= 4
if n % 8 == 7:
return 4
a = 0
while a**2 <= n:
b = int((n - a**2)**0.5)
if a**2 + b**2 == n:
return (not not a) + (not not b)
a += 1
return 3
本文涉及引用來自于leetcode
作者：EiletXie
鏈接：https://leetcode-cn.com/problems/perfect-squares/solution/yan-du-you-xian-sou-suo-java-by-eiletxie/
來源：力扣（LeetCode）
