题解 | #最少的完全平方数#

dp 问题, 设置 dp[i] 表示能组成 i 的最少完全平方数, dp[0] = 0, dp[i] = min(dp[i - j * j] + 1, dp[i]) j < i dp[i - j * j] 表示上一个组成完全平方数的最少值,因为每个正数都可以是完全平方数(1 + 1 + ... + 1),最多次数可以为 n，遍历数组，根据转移方程得出每个状态位的dp值

class Solution:
    def numSquares(self , n: int) -> int:
        # write code here
        
        dp = [n for _ in range(n + 1)]
        dp[0] = 0
        for i in range(1, n + 1):
            if int(i ** 0.5) ** 2 == i:
                dp[i] = 1
            else:
                # 由于 i 为多个完全平方数相加,则 j 不会大于 int(i ** 0.5) + 1 
                for j in range(1, int(i ** 0.5) + 1):
                    dp[i] = min(dp[i], dp[i - j ** 2] + 1)
        return dp[-1]
        """
        dp = [float("inf") for _ in range(n + 1)]
        dp[0] = 0
        for i in range(1, n + 1):
            for j in range(1, int(n ** 0.5) + 1):
                dp[i] = min(dp[i], dp[i - j * j] + 1)
        return dp[-1]
        """