【算法挨揍日记】day44——518. 零钱兑换 II、279. 完全平方数

旧城等待， 2024-02-05 21:22 45阅读 0赞

## 518. 零钱兑换 II ##

[518. 零钱兑换 II][518. _ II]

### 题目描述： ###

给你一个整数数组 `coins` 表示不同面额的硬币，另给一个整数 `amount` 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 `0` 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

![a184aa54475f47aeaaf00f86f39f1af2.png][]

### 解题思路： ###

算法思路：

先将问题「转化」成我们熟悉的题型。

i.  在⼀些物品中「挑选」⼀些出来，然后在满⾜某个「限定条件」下，解决⼀些问题，⼤概率

是背包模型；

ii.  由于每⼀个物品都是⽆限多个的，因此是⼀个「完全背包」问题。

接下来的分析就是基于「完全背包」的⽅式来的。

1.  状态表⽰：

dp\[i\]\[j\]  表⽰：从前  i  个硬币中挑选，总和正好等于  j  ，⼀共有多少种选法。

2.  状态转移⽅程：

线性  dp  状态转移⽅程分析⽅式，⼀般都是「根据最后⼀步」的状况，来分情况讨论。但是最后

⼀个物品能选很多个，因此我们的需要分很多情况：

i.  选  0  个第  i  个硬币：此时相当于就是去前  i - 1  个硬币中挑选，总和正好等于  j  。

此时最少的硬币个数为  dp\[i - 1\]\[j\]  ；

ii.  选  1  个第  i  个硬币：此时相当于就是去前  i - 1  个硬币中挑选，总和正好等于  j -

v\[i\]  。因为挑选了⼀个  i  硬币，此时最少的硬币个数为  dp\[i - 1\]\[j -

coins\[i\]\] + 1  ；

ii.  选  2  个第  i  个硬币：此时相当于就是去前  i - 1  个硬币中挑选，总和正好等于  j

\- 2 \* coins  。因为挑选了两个  i  硬币，此时最少的硬币个数为  dp\[i - 1\]\[j -

2 \* coins\[i\]\] + 2  ；

iv.  ......

结合我们在完全背包⾥⾯的「优化思路」，我们最终得到的状态转移⽅程为：

dp\[i\]\[j\] = dp\[i - 1\]\[j\] + dp\[i\]\[j - coins\[i\]\] + 1  。

这⾥教给⼤家⼀个技巧，就是相当于把第⼆种情况  dp\[i - 1\]\[j - coins\[i\]\] + 1  ⾥

⾯的  i - 1  变成  i  即可。

3.  初始化：

初始化第⼀⾏即可。

第⼀⾏表⽰没有物品，没有物品正好能凑能和为  0  的情况。因此  dp\[0\]\[0\] = 1  ，其余位置都

是  0  种情况。

4.  填表顺序：

根据「状态转移⽅程」，我们仅需「从上往下」填表即可。

5.  返回值：

根据「状态表⽰」，返回  dp\[n\]\[V\]  。

### 解题思路： ###

class Solution {
    public:
        int change(int amount, vector<int>& coins) {
            int n=coins.size();
            vector<vector<int>>dp(n+1,vector<int>(amount+1));
            dp[0][0]=1;
            for(int i=1;i<=n;i++)
            {
                for(int j=0;j<=amount;j++)
                {
                    dp[i][j]+=dp[i-1][j];
                    if(j>=coins[i-1]) dp[i][j]+=dp[i][j-coins[i-1]];
                }
            }
            return dp[n][amount];
        }
    };

### 空间优化后的代码： ###

class Solution {
    public:
        int change(int amount, vector<int>& coins) {
            int n=coins.size();
            vector<int>dp(amount+1);
            dp[0]=1;
            for(int i=1;i<=n;i++)
            {
                for(int j=coins[i-1];j<=amount;j++)
                {
                    dp[j]+=dp[j-coins[i-1]];
                }
            }
            return dp[amount];
        }
    };

## 279. 完全平方数 ##

[279. 完全平方数][279.]

### 题目描述： ###

###  ###

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

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

### 解题思路： ###

算法思路：

这⾥给出⼀个⽤「拆分出相同⼦问题」的⽅式，定义⼀个状态表⽰。（⽤「完全背包」⽅式的解法

就仿照之前的分析模式就好啦~~）

为了叙述⽅便，把和为  n  的完全平⽅数的最少数量简称为「最⼩数量」。

对于  12  这个数，我们分析⼀下如何求它的最⼩数量。

▪  如果  12  本⾝就是完全平⽅数，我们不⽤算了，直接返回  1  ；

▪  但是  12  不是完全平⽅数，我们试着把问题分解⼀下：

1.  情况⼀：拆出来⼀个  1  ，然后看看  11  的最⼩数量，记为  x1  ；

2.  情况⼆：拆出来⼀个  4  ，然后看看  8  的最⼩数量，记为  x2  ；（为什么拆出来  4  ，

⽽不拆出来  2  呢？）

3.  情况三：拆出来⼀个  8  ......

其中，我们接下来求  11 、 8  的时候，其实⼜回到了原来的问题上。

因此，我们可以尝试⽤  dp  的策略，将  1 2 3 4 6  等等这些数的最⼩数量依次保存起来。再求

较⼤的  n  的时候，直接查表，然后找出最⼩数量。

1.  状态表⽰：

dp\[i\]  表⽰：和为  i  的完全平⽅数的最少数量。

2.  状态转移⽅程：

对于  dp\[i\]  ，根据思路那⾥的分析我们知道，可以根据⼩于等于  i  的所有完全平⽅数  x  进⾏

划分：

▪  x = 1  时，最⼩数量为：  1 + dp\[i - 1\]  ；

▪  x = 4  时，最⼩数量为：  1 + dp\[i - 4\]  ......

⼀直枚举到  x <= i  为⽌。

为了⽅便枚举完全平⽅数，我们采⽤下⾯的策略：  for(int j = 1; j \* j <= i; j++)

综上所述，状态转移⽅程为：

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

3.  初始化：

当  n = 0  的时候，没法拆分，结果为  0  ；

当  n = 1  的时候，显然为  1  。

4.  填表顺序：

从左往右。

5.  返回值：

根据题意，返回  dp\[n\]  的值。

### 解题代码： ###

class Solution {
    public:
        int numSquares(int n) {
            vector<int> dp(n + 1);
            dp[1] = 1;                   // 初始化
            for (int i = 2; i <= n; i++) // 枚举每个数
            {
                dp[i] = 1 + dp[i - 1];           // ⾄少等于 1 + dp[i - 1]
                for (int j = 2; j * j <= i; j++) // ⽤⼩于 i 的完全平⽅数划分区间
                    dp[i] =
                        min(dp[i], dp[i - j * j] + 1); // 拿到所有划分区间内的最⼩值
            }
            // 返回结果
            return dp[n];
        }
    };

### ” ###

[518. _ II]: https://leetcode.cn/problems/coin-change-ii/
[a184aa54475f47aeaaf00f86f39f1af2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/39fd1b2a0200421a86a5f3702450ce48.png
[279.]: https://leetcode.cn/problems/perfect-squares/