代码随想录笔记_动态规划_279完全平方数

代码随想录二刷笔记记录

LC279.完全平方数

---

题目

完全背包

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

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

示例 1：

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

示例 2：

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

---

思路分析

思路：

以 [1,4,9,16] 为例，则

完全平方数的集合[1,4,9,16] 即为物品，求和 n 即为背包容量。

问题转化为从 [1,4,9,16] 中取出能组成 n 的最少物品

动态规划五部曲

1.确定dp数组及其下标的含义

dp[j] : 能组成背包容量j的最少完全平方数的数量
1

2.确定递推公式

dp[j] = Math.min(dp[j],dp[j - nums[i]] + 1);
完全平方数组 nums[i] 可以拆解为 i*i,则
dp[j] = Math.min(dp[j],dp[j - i*i] + 1);
1
2
3

3.初始化

根据递推公式可知
dp[0]初始化为0，其余初始化为 Integer.MAX_VALUE，避免被初始值覆盖

4.遍历顺序

求组合就先遍历物品后遍历背包,求排列就先遍历背包后遍历物品
本题所求的是能装满背包的最少个数，先遍历哪一个都可以

for(int j = 0;j <= n;j++){//先遍历背包
	for(int i = 1;ii <= j;i++){
		dp[j] = Math.min(dp[j], dp[j - ii] + 1);
	}
}
1
2
3
4
5

5.推演分析

以 n = 5 为例，max = Integer.MAX_VALUE

---

代码实现

完整代码实现

public int numSquares(int n) {
        //初始化
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        //遍历顺序
        for(int j = 0;j <= n;j++){//遍历背包容量j
            for(int i = 1;i*i <= j;i++){//遍历物品:完全平方数i
                dp[j] = Math.min(dp[j],dp[j - i*i] + 1);
            }
        }
        return dp[n];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

---