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

Allenlzcoder

已于 2025-04-09 01:19:57 修改

阅读量342

点赞数 7

分类专栏：力扣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];
    }
}