划分型动态规划——完全平方数

水深无声 2022-10-27 12:06 114阅读 0赞

#  #

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
    输出: 3 
    解释: 12 = 4 + 4 + 4.

### 1、题目分析 ###

从题目的提问方式，能够很明显的看出这是个最值类型的动态规划。

### 2、确定状态 ###

最后一步：关注最后策略中最后一个完全平方数j\*j；最后策略中n-j\*j也一定被划分成最少的完全平方数之和。

因此我们可以假设f\[i\]表示i最少被分成几个完全平方数之和

### 3、转移方程 ###

假设f\[i\]表示i最少被分成几个完全平方数之和

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]

### 4、初始条件和边界情况 ###

初始条件：0被分成0个完全平方数之和，f\[0\]=0

### 5、计算顺序 ###

从小到大，答案是f\[N \]

### 6、代码实现 ###

class Solution:
        def numSquares(self, n: int) -> int:
            square_nums = [i**2 for i in range(0, int(math.sqrt(n))+1)]        
            dp = [float('inf')] * (n+1)
            dp[0] = 0 
            for i in range(1, n+1):
                for square in square_nums:
                    if i < square:
                        break
                    dp[i] = min(dp[i], dp[i-square] + 1)
            return dp[-1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]: /images/20221024/4d68d9d8662b469f8776fd38480cf140.png

发表评论取消回复

表情：

评论列表（有 0 条评论，114人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode_动态规划_中等_279.完全平方数

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给你一个整数 n ，返回和为 n 的完全平方数的最少数量。完全平方数是一个

深藏阁楼爱情的钟/ 2023年10月06日 22:45/ 0 赞/ 8 阅读

相关【C】完全平方数

使用VS2019 ISO C++14 标准 (/std:c++14) 完全平方数判断 > 一个整数n（n小于1000），它加上100后是一个完全平方数，再加上168又

「爱情、让人受尽委屈。」/ 2023年03月14日 10:51/ 0 赞/ 184 阅读

相关 279. 完全平方数(完全背包)

\\\ 解题思路一个典型的完全背包问题 \\\ 代码 class Solution { public: int numSquares(i

系统管理员/ 2023年01月12日 13:59/ 0 赞/ 194 阅读

相关 279. 完全平方数

题目： [279. 完全平方数][279.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_te

你的名字/ 2022年11月25日 00:58/ 0 赞/ 192 阅读

相关划分型动态规划——完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。示例 1: 输入:

水深无声/ 2022年10月27日 12:06/ 0 赞/ 115 阅读

相关划分型动态规划——解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码： ‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 给定一个只包含数字的非空字符串，请计

左手的ㄟ右手/ 2022年10月27日 12:06/ 0 赞/ 171 阅读

相关划分型动态规划——书籍复制

给定 n 本书, 第 i 本书的页数为 pages\[i\]. 现在有 k 个人来复印这些书籍, 而每个人只能复印编号连续的一段的书, 比如一个人可以复印 pages\

分手后的思念是犯贱/ 2022年10月27日 06:30/ 0 赞/ 144 阅读

相关 leetcode 279. Perfect Squares | 279. 完全平方数（动态规划，Java）

题目 [https://leetcode.com/problems/perfect-squares/][https_leetcode.com_problems_perfe

左手的ㄟ右手/ 2022年10月11日 13:50/ 0 赞/ 164 阅读

相关 279. 完全平方数

2021-06-11 LeetCode每日一题链接：[https://leetcode-cn.com/problems/perfect-squares/][https_

女爷i/ 2022年10月06日 06:52/ 0 赞/ 205 阅读

相关 279. 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。给你一个整数 n ，返回和为 n

心已赠人/ 2022年10月06日 05:42/ 0 赞/ 214 阅读