279. 完全平方数——组成和的完全平方数的个数最少

冷不防 2023-10-04 08:45 6阅读 0赞

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

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

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

**示例 1：**

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

**示例 2：**

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

**提示：**

*  `1 <= n <= 104`

package Solution279;
    
    import java.util.ArrayList;
    
    class Solution {
    
    	public int numSquares(int n) {
    		ArrayList<Integer> coins = new ArrayList<Integer>();
    		for (int i = 1; i <= Math.sqrt(n); i++) {
    			if (i * i <= n) {
    				coins.add(i * i);
    			}
    		}
    		int dp[] = new int[n + 1];
    		dp[0] = 0;
    		for (int i = 1; i <= n; i++) {
    			dp[i] = n + 1;
    		}
    		for (int coin : coins) {
    			for (int amt = 1; amt <= n; amt++) {
    				if (amt >= coin) {
    					dp[amt] = Math.min(dp[amt], 1 + dp[amt - coin]);
    				}
    			}
    		}
    		int minCoinsReq = dp[n] != n + 1 ? dp[n] : -1;
    		return minCoinsReq;
    	}
    
    	public static void main(String[] args) {
    
    		Solution sol = new Solution();
    
    		int n = 12;
    
    		System.out.println(sol.numSquares(n));
    	}
    
    }

类似题目：322. 零钱兑换——凑成总金额所需的最少的硬币个数

发表评论取消回复

表情：

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

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

相关阅读

相关 279.完全平方数

279.完全平方数题干描述解题思路 1. 确定dp数组（dp table）以及下标的含义 2. 确定递推公式 3.

╰半夏微凉°/ 2023年10月16日 17:06/ 0 赞/ 58 阅读

相关 279. 完全平方数——组成和的完全平方数的个数最少

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

冷不防/ 2023年10月04日 08:45/ 0 赞/ 7 阅读

相关 Leetcode 279. 完全平方数

Leetcode 279. 完全平方数 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcode-cn.

墨蓝/ 2023年02月14日 03:06/ 0 赞/ 126 阅读

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

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

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

相关 279. 完全平方数

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

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

相关 279. 完全平方数

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

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

相关 279. 完全平方数

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

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

相关 LeetCode 279 完全平方数

https://leetcode-cn.com/problems/perfect-squares/ ![在这里插入图片描述][2f27a9f8cc0b4daeab65061

柔光的暖阳◎/ 2022年09月03日 10:24/ 0 赞/ 305 阅读

相关 leetcode 279 完全平方数

前言题目：[279. 完全平方数][279.] 参考题解：[完全平方数-代码随想录][-] -------------------- 提交代码完全背包问题

刺骨的言语ヽ痛彻心扉/ 2022年08月28日 03:52/ 0 赞/ 290 阅读

相关 LeetCode279——完全平方数

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCod

偏执的太偏执、/ 2022年03月10日 07:24/ 0 赞/ 299 阅读