完全平方数-动态规划279

没看答案，动态规划-完全背包问题。

import math

class Solution:
    def numSquares(self, n: int) -> int:
        '''
        basecase: 初始化只考虑1的情况
        state: 由于int(sqrt(n))的的平方一定小于等于n，所以物品相当于candidate数组中的元素，背包重量为n
               dp[j]表示背包重量为j时的最少完全平方数
        transfer: 遍历所有物品，dp[i]由不拿这个物品(dp[j])和拿这个物品+1(dp[j-candidate[i]]+1)中的最小值决定
        '''
        mid = int(math.sqrt(n))
        candidate = [i**2 for i in range(1, mid+1)]
        length = len(candidate)

        dp = [0] + [i for i in range(1, n+1)]

        for i in range(1, length):
            for j in range(n+1):
                if j >= candidate[i]:
                    dp[j] = min(dp[j], dp[j-candidate[i]] + 1)
        
        return dp[-1]