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

给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ,返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。

示例 1:

输入:n = 12
输出:3
解释:12 = 4 + 4 + 4
示例 2:

输入:n = 13
输出:2
解释:13 = 4 + 9
 
提示:

1 <= n <= 104

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/perfect-squares

参考:

  • 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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/perfect-squares

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
}