【Leetcode刷题Python】279. 完全平方数

1 题目

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

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

示例 1：

输入：n = 12 输出：3 解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13 输出：2 解释：13 = 4 + 9

2 解析

状态：f[i]表示最少需要多少个数的平方来表示整数 i。

这些数必然落在区间。我们可以枚举这些数，假设当前枚举到 jj，那么我们还需要取若干数的平方，构成 i − j 2 i-j^2 i−j2 。此时我们发现该子问题和原问题类似，只是规模变小了。这符合了动态规划的要求，于是我们可以写出状态转移方程。

f [ i ] = 1 + min ⁡ j = 1 ⌊ i ⌋ f [ i − j 2 ] f[i]=1+\min_{j=1}^{\lfloor\sqrt{i}\rfloor}{f[i-j^2]} f[i]=1+j=1min⌊i ​⌋​f[i−j2] 其中 f[0]=0为边界条件，实际上我们无法表示数字 0，只是为了保证状态转移过程中遇到 j恰为 i \sqrt{i} i ​ 的情况合法。

3 Python实现

class Solution:
    def numSquares(self, n: int) -> int:
        f = [0]*(n+1)
        for i in range(1,n+1):
            j = 1
            minn = float('inf')
            while j*j