【C++】【提高】中国梦

Question

题目描述
小 Z 整理完房间时间已经不早了，简单洗漱一下就上床睡觉了，自从进入初三后小 Z 已经有很久没有做梦了，不做梦的主要原因是学习强度太大加上睡得较晚，一旦睡着就睡 得特别沉，沉到没有梦的地步。今晚小 Z 的大脑皮层特别兴奋，大约是由于白天在 CZ 中 学上的课实在太精彩了，这不小 Z 刚睡着就进入了梦乡。在梦里小 Z 梦见自己代表祖国赴 B 国参加了国际信息学奥林匹克竞赛（International Olympiad in Informatics，简称 IOI）并获得了金牌，颁奖会结束后小 Z 想到附近的超市去买些礼物带回国送给班里的小 伙伴们，小 Z 心想 B 国的巧克力代表了爱的愿望、大众的迷恋，是食物中的王者，早在 19 世纪就已经闻名于世了，给小伙伴们每人买一盒巧克力肯定会大受欢迎。于是小 Z 一进超市就直奔装有巧克力的货架，一口气拿了 40 盒 Godiva 巧克力，然后到收银台去排队结帐， 轮到小 Z 结账时，他发现自己身上只有一张大面额的 B 国钞票了，于是他把这张钞票递了 过去，收银员迅速在收银机上算出了要找给小 Z 的金额，然后打开钱柜准备找钱，小 Z 看 到钱柜里的硬币按面额从大到小整整齐齐地摆放着，一种面额的硬币垒成一列，见此情景 小 Z 一下就来了灵感，心想少年宫正在为本次活动征集试题呢，就拿这个找零问题考考小 朋友们不是挺好吗？小 Z 回到宾馆立刻打开笔记本开始命题：
已知收银员要找给小 Z 的金 额 N、钱柜里的硬币种类 K 以及 K 种硬币的面额，计算有多少种不同的找零方法？ 这里的 “不同”是指所找零钱至少有一种硬币的数量不相同。假设现在只有 2 种硬币，一种面额是 5 分，另一种面额是 1 分，要找给小 Z 的金额是 8 分钱，可以给小 Z 找 1 个五分硬币加3 个一分硬币，或者找 8 个一分硬币。用 3 个一分硬币加 1 个五分硬币本质上与 1 个五分硬币加 3 个一分硬币没有任何区别，因此只可以用两种不同的方式找出八分钱。
输入
输入数据第一行有两个用空格隔开的整数 N 和 K，其中 1≤N≤300，表示超市收银员 要找给小 Z 的金额，1≤K≤8，表示收银员的钱柜里共有 K 种不同面额的硬币。

第 2 到 K+1 行每行包含一个正整数 Ci，其中 1≤Ci≤100，表示一种硬币的面额，在输入数据中硬币 面额按降序排列（从最大到最小）。 不同种类的硬币面额各不相同，每种硬币都取之不尽 用之不竭。

输出
输出数据仅有一行包含一个整数，表示超市收银员可能的找零方案数。答案保证不会 超出长整型范围。需要注意的是如果没有面额为 1 分的硬币，有些金额将无法找零，此时 结果就输出 0。
样例输入
83 5
50
25
10
5
1
样例输出
159
提示
【样例解释】
输入详解：收银员要找给小 Z 金额 83 分，共有 5 种硬币，面额分别为：50,25,10, 5,1

输出详解：以下是全部 159 种找零方案中的 前 15 种和最后一种:

【数据范围】
10%的数据满足：N≤50，K≤3，Ci≤10
30%的数据满足：N≤100，K≤5，Ci≤20
60%的数据满足：N≤100，K≤7，Ci≤50
100%的数据满足：N≤300，K≤8，Ci≤100

错误代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
    
    return 0;
}

Answer 1

引自免费微信小程序：皆我百晓生

为了解决这个问题，我们可以使用动态规划的方法。首先定义一个二维数组dp，其中dp[i][j]表示在前i种硬币中找到j元的不同方法数。初始状态是dp[0][0]=1，因为没有硬币时，找不到任何金额，所以只有0元的一种情况。接下来的状态转移方程为：对于每种硬币ci，如果ci<=j，那么dp[i][j] = dp[i][j-ci] + dp[i-1][j]，表示可以选择用当前硬币ci，也可以选择不用。最后的结果就是dp[K][N]。

下面是完整的C++代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;

    vector<int> coins(K);
    for (int i = 0; i < K; ++i) {
        cin >> coins[i];
    }

    // 初始化dp数组
    vector<vector<int>> dp(K + 1, vector<int>(N + 1, 0));
    dp[0][0] = 1;

    // 动态规划
    for (int i = 1; i <= K; ++i) {
        for (int j = 1; j <= N; ++j) {
            if (coins[i - 1] <= j) {
                dp[i][j] = dp[i][j - coins[i - 1]] + dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    cout << dp[K][N] << endl;

    return 0;
}

这段代码首先读入总金额N、硬币种类数K以及每种硬币的面额，然后初始化dp数组，并通过两层循环进行动态规划计算，最后输出dp[K][N]作为结果。注意，代码中使用了vector容器来存储硬币面额和动态规划数组，这样可以避免硬编码长度限制。