笔试时间：2023年7月27日 秋招提前批

第一题

题目：零钱兑换

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。

如果无解，请返回-1.

输入描述

第一行给定两个正整数分别是 n 和 aim 分别表示数组 arr 的长度和要找的钱数。

第二行给定 n 个正整数表示 arr 数组中的所有元素

输出描述

输出组成 aim 的最少货币数

样例输入

示例1:

3 20

5 2 3

示例2:

3 0

5 2 3

样例输出

示例1:

4

说明：最少用四个 5 元凑成 20 元

示例2:

0

参考题解

此题是典型的完全背包问题。

状态转移方程式：dp[i][j]考虑前i个硬币，凑出 j 元最少需要的硬币数。dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i])

容器规模：i 的范围是[0, coins.length] j 的范围是 [0, amount]

base case：dp[0][j]表示考虑前0个硬币凑出j的最少硬币数，除了dp[0][0] = 0以外，其余的均凑不了，也就是没有硬币的情况下，只能凑出0，其他的金额都凑不了，因此这里用一个比较大的数字表示（因为amount最大是10^4，因此我们用10001表示最大值）

顺序：i = 1 开始填表

可以利用滚动数组进行优化

C++：

#include <vector>
#include <algorithm>
#include <climits>

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

Java：

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, 10001);
        dp[0] = 0;
        for (int i = 1 ; i <= coins.length ; i++) {
            for (int j = coins[i - 1] ; j <= amount ; j++) {
                    d