完全平方数

题目描述

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

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

示例 1：

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

题目链接：https://leetcode.cn/problems/perfect-squares

文章讲解：https://programmercarl.com/0279.完全平方数.html

思路

依然使用完全平方数凑成n。背包容量为整数n，物品为完全平方数。

问 和为 n 的完全平方数的最少数量 就是问物品所需最少数量。从示例上看物品可以重复使用。

所以这是一个完全背包问题，和零钱兑换一模一样

动规五部曲

1、dp数组及下标含义

dp[j]：凑足整数 j 所需完全平方数的最少数量为dp[j]

2、递推公式

在【0，i*i 】完全平方数 中考虑，凑足和为 j 时 完全平方数数量最少 有两种情况：

情况1、 j 小于 i*i ，这时 i*i 根本放不进背包，溢出了。意味着[0,i*i] 时dp[j] == [0,(i-1)*(i-1)]时dp[j]

情况2、 j 大于等于 i*i，这时考虑 i*i 在不在其中。

- 情况2.1 在，那么`dp[j] = dp[j-i*i]+1`。
- 情况2.2 不在，那么`dp[j] = dp[j]`，和第一种情况相同
- 情况2.1和2.2之间选个小的

dp[j] = min(dp[j],dp[j-i*i]+1);

3、dp数组初始化

因为整数n从1开始，因此 dp[0] 没有意义，那么我们初始化成什么？。很明显dp[1]=1，那么为了能够满足递推公式求出dp[1]，应该dp[0]=0, 而dp[1] 初始化为比1大的数。但是为了保持一致，顺利求出其他非0下标的dp[j]，因此其余非0下标的dp[j]为INT_MAX。

4、确定遍历顺序

外层for遍历背包，内层for遍历物品，还是外层for遍历物品，内层for遍历背包，都是可以的！

5、举例推导

n为5例，dp状态图如下：

遍历背包再遍历物品的示例，未显示完全，

代码实现

int numSquares(int n) {
    std::vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;
    for(int i = 1;i*i <= n;i++){
        for(int j = i*i;j <= n;j++){
            dp[j] = std::min(dp[j],dp[j - i*i] + 1); 
        }
    }
    return dp[n];
}