【重点】【DP】279.完全平方数

Allenlzcoder

已于 2025-06-08 21:14:20 修改

阅读量349

点赞数 7

CC 4.0 BY-SA版权

分类专栏：力扣Top100 文章标签：算法 dp

于 2023-12-26 23:37:53 首次发布

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/135233656

力扣Top100 专栏收录该内容

100 篇文章

订阅专栏

文章介绍了使用动态规划方法解决numSquares问题，通过对比记忆和与完全背包问题类似思路，找到分解整数为平方数的最小数量。关键代码展示了如何计算给定整数n所需的最小平方数个数。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

法1：dp

跟兑换零钱相同思路，对比记忆！！！
跟完全背包问题的解法一致！

Python

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [n] * (n+1) # dp[i]表示和为i最小数量
        dp[0] = 0 # 初始化非常重要!!!
        for i in range(1, n+1):
            k = 1
            while k * k <= i:
                dp[i] = min(dp[i - k*k] + 1, dp[i])
                k += 1
        
        return dp[n]

Java

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            int min = n;
            for (int k = 1; k * k <= i; ++k) {
                min = Math.min(min, 1 + dp[i - k * k]);
            }
            dp[i] = min;
        }

        return dp[n];
    }
}