AlgoPressAppearance
0279-完全平方数
https://leetcode.cn/problems/perfect-squares
给定正整数 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 <= 10^4
基本思路【ME】
定义 dp, dp[i] 表示 i 所在位置的最小完全平方数的个数 状态转移方程: 如果 i 就是 完全平方数，则 dp[i] = 1, n < 10^4 我们可以遍历检测 注意： 每次循环检测 i 是否是完全平方数，会非常耗时，LeetCode 提交会超时 我们可以初始化的时候，就把完全平方数所在的位置先置为1。
否则拆分 dp[i] = min(dp[j] + dp[i-j],dp[i])
参考代码
csharp
public class Solution {
public int NumSquares(int n) {
int[] dp = new int[n+1];
//初始化默认值
for(int i=1; i<dp.Length; i++){
dp[i] = int.MaxValue;
}
//初始化已经是完全平方根的数
for(int i=1; i<dp.Length; i++){
if(i*i <=n){
dp[i*i] = 1;
}
}
for(int i=2; i<=n; i++){
for(int j=1;j<i;j++){
dp[i] = Math.Min(dp[i], dp[j] + dp[i-j]);
}
}
return dp[n];
}
}
参考代码2：复习 2022-04-02
csharp
public class Solution {
public int NumSquares(int n) {
// 动态规划：完全背包
// dp[i] 表示凑成 i 的最小数量
int[] dp = new int[n+1];
for(int i=1; i<=n; i++){
dp[i] = int.MaxValue;
}
for(int i=1; i * i <= n; i++){
dp[i*i] = 1;
}
//状态转移
for(int i=1; i<=n; i++){
for(int j=1; j*j<i;j++){
dp[i] = Math.Min(dp[i],dp[i-j*j]+1);
}
}
return dp[n];
}
}
复习：完全背包
注意: 因为取最小值，所以要设置默认值为最大。 2. dp[ii]不需要单独设置值，因为 dp[j-ii] + 1 = dp[0]+1
csharp
public class Solution {
public int NumSquares(int n) {
//完全背包，先遍历物品
int[] dp = new int[n+1]; //dp表示凑成j的最小数量
Array.Fill(dp,int.MaxValue);
dp[0] = 0; //
for(int i=1;i*i<=n;i++){
for(int j=1;j<=n;j++){
if(j>=i*i && dp[j-i*i] != int.MaxValue){
dp[j] = Math.Min(dp[j],dp[j-i*i] + 1);
}
}
}
return dp[n];
}
}
复习:20220630
csharp
public class Solution {
public int NumSquares(int n) {
//完全背包问题，dp[i] 表示凑成i的完全平方数的个数
//物品就是完全平方数
int[] dp = new int[n+1];
Array.Fill(dp,n); //默认设置最大值
dp[0] = 0; //初始化凑成0的个数为0
for(int i=1; i*i<=n; i++){ //遍历物品
for(int j=1; j<=n; j++){ //遍历背包
if(j>=i*i){
dp[j] = Math.Min(dp[j],dp[j-i*i]+1);
}
}
}
return dp[n];
}
}