# 0279-完全平方数(0279 complete square)-其他

## 0279-完全平方数(0279 complete square)

1 <= n <= 104

• https://leetcode-cn.com/problems/perfect-squares/solution/dai-ma-sui-xiang-lu-279-wan-quan-ping-fa-9ieo/

### python

``````# 0279.完全平方数

class Solution:
def numSqaures(self, n: int) -> int:
"""
动态规划，完全背包， 先背包再物品
:param n:
:return:
"""
nums = [i**2 for i in range(1, n+1) if i**2 <= n]
dp = [10**4] * (n+1)
dp[0] = 0
for j in range(1, n+1):
for i in range(len(nums)):
if j >= nums[i]:
dp[j] = min(dp[j], dp[j-nums[i]]+1)
return dp[n]

def numSqaures2(self, n: int) -> int:
"""
动态规划，完全背包， 先物品再背包
:param n:
:return:
"""
nums = [i**2 for i in range(1, n+1) if i**2 <= n]
dp = [10**4] * (n+1)
dp[0] = 0
for i in range(len(nums)):
for j in range(nums[i], n+1):
dp[j] = min(dp[j], dp[j-nums[i]]+1)
return dp[n]
``````

### golang

``````package dynamicPrograming

import "math"

// 动态规划-完全背包-先背包再物品
func numSquares(n int) int {
dp := make([]int, n+1)
dp[0] = 0
for j:=1;j<=n;j++ { // bag
dp[j] = math.MaxInt32
for i:=1;i<=n;i++ { // 物品
if j >= i*i {
dp[j] = min(dp[j], dp[j-i*i]+1)
}
}
}
return dp[n]
}

// 动态规划-完全背包-先物后包
func numSquares2(n int) int {
dp := make([]int, n+1)
dp[0] = 0
for i:=1;i<=n;i++ {
dp[i] = math.MaxInt32
}
// 物品
for i:=1;i<=n;i++ {
// bag
for j:=i*i;j<=n;j++ {
dp[j] = min(dp[j], dp[j-i*i]+1)
}
}
return dp[n]
}

func min(a,b int) int {
if a < b {
return a
}
return b
}
``````
————————

Given positive integer   n. Find several complete squares (e.g   1, 4, 9, 16,…) so that their sum is equal to n. You need to minimize the number of complete squares of the composition sum.

Give you an integer n and return the minimum number of complete squares with a sum of n.

A perfect square is an integer whose value is equal to the square of another integer; In other words, its value is equal to the product of the self multiplication of an integer. For example, 1, 4, 9, and 16 are perfect squares, while 3 and 11 are not.

Example   1：

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4
Example 2:

Input: n = 13
Output: 2
Interpretation: 13 = 4 + 9

Tips:

1 <= n <= one hundred and four

reference resources:

• https://leetcode-cn.com/problems/perfect-squares/solution/dai-ma-sui-xiang-lu-279-wan-quan-ping-fa-9ieo/

### python

``````# 0279.完全平方数

class Solution:
def numSqaures(self, n: int) -> int:
"""
动态规划，完全背包， 先背包再物品
:param n:
:return:
"""
nums = [i**2 for i in range(1, n+1) if i**2 <= n]
dp = [10**4] * (n+1)
dp[0] = 0
for j in range(1, n+1):
for i in range(len(nums)):
if j >= nums[i]:
dp[j] = min(dp[j], dp[j-nums[i]]+1)
return dp[n]

def numSqaures2(self, n: int) -> int:
"""
动态规划，完全背包， 先物品再背包
:param n:
:return:
"""
nums = [i**2 for i in range(1, n+1) if i**2 <= n]
dp = [10**4] * (n+1)
dp[0] = 0
for i in range(len(nums)):
for j in range(nums[i], n+1):
dp[j] = min(dp[j], dp[j-nums[i]]+1)
return dp[n]
``````

### golang

``````package dynamicPrograming

import "math"

// 动态规划-完全背包-先背包再物品
func numSquares(n int) int {
dp := make([]int, n+1)
dp[0] = 0
for j:=1;j<=n;j++ { // bag
dp[j] = math.MaxInt32
for i:=1;i<=n;i++ { // 物品
if j >= i*i {
dp[j] = min(dp[j], dp[j-i*i]+1)
}
}
}
return dp[n]
}

// 动态规划-完全背包-先物后包
func numSquares2(n int) int {
dp := make([]int, n+1)
dp[0] = 0
for i:=1;i<=n;i++ {
dp[i] = math.MaxInt32
}
// 物品
for i:=1;i<=n;i++ {
// bag
for j:=i*i;j<=n;j++ {
dp[j] = min(dp[j], dp[j-i*i]+1)
}
}
return dp[n]
}

func min(a,b int) int {
if a < b {
return a
}
return b
}
``````