HackMD
279.Perfect Squares
tags: Medium,DP,Math
題目描述
Given an integer n, return the least number of perfect square numbers that sum to n.
A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
範例
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
解答
Javascript
解法一
根據四平方和定理，每一個正整數均可以表示為4個整數的平方和。
function numSquares(n) {
const squares = [];
for (let i = 1; i <= n; i++) {
if (Math.sqrt(i) % 1 === 0) {
if (i === n) return 1;
for (let j = 0; j < 4; j++) {
squares.push(i);
}
}
}
// Two Sum
let right = squares.length - 1;
for (let i = 0; i < squares.length; i++) {
const sum = squares[i] + squares[right];
if (sum === n) return 2;
if (sum > n) {
right--;
}
}
// Three Sum
for (let i = 0; i < squares.length - 2; i++) {
let left = i + 1;
let right = squares.length - 1;
while (left < right) {
const sum = squares[i] + squares[right] + squares[left];
if (sum === n) return 3;
if (sum > n) {
right--;
} else {
left++;
}
}
}
return 4; // 4sum沒必要
}
Marsgoat Nov 22, 2022
解法二
跟大家學的DP
function numSquares3(n) {
const dp = new Array(n + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= n; i++) {
for (let j = 1; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
Marsgoat Nov 23, 2022
Python
很慢的DP
class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
# init
dp = [0] + [float("inf") for _ in range(n)]
num = 1
square_num = 1
while (square_num <= n):
# update dp array from square num
for idx in range(square_num, n+1):
dp[idx] = min(dp[idx], dp[idx - square_num] + 1)
num += 1
square_num = num* num
return dp[n]
DT Nov 22, 2022
依舊很慢的 DP
class Solution:
def numSquares(self, n: int) -> int:
table = [i for i in range(1, n+1)]
good_point = []
for i in range(1, n+1):
if int(i**0.5) == i**0.5:
table[i-1] = 1
good_point.append(i)
else:
for j in good_point:
if table[j-1] == 1:
v = table[j-1] + table[i-j-1]
if v < table[i-1]:
table[i-1] = v
return table[n-1]
gpwork4u Nov 22, 2022
C++
也很慢的DP
int numSquares(int n) {
vector<int> dp(n+1, INT_MAX);
dp[0] = 0;
for(int i = 0; i <= n; i++)
{
for(int j = 1; i + j * j <= n; j++)
dp[i+j*j] = min(dp[i+j*j], dp[i]+1);
}
return dp[n];
}
XD Nov 22, 2022
