B3635 硬币问题

题目描述

今有面值为 1、5、11 元的硬币各无限枚。

想要凑出 nn 元，问需要的最少硬币数量。

输入格式

仅一行，一个正整数 nn。

输出格式

仅一行，一个正整数，表示需要的硬币个数。

输入输出样例

输入 #1复制

15

输出 #1复制

3

输入 #2复制

12

输出 #2复制

2

说明/提示

样例解释

对于样例数据 1，最佳方案是 15=5+5+515=5+5+5，使用到 3 枚硬币。

对于样例数据 2，最佳方案是 12=11+112=11+1，使用到 2 枚硬币。

数据规模与约定

对于 100%100% 的数据，保证 n≤106n≤106。

代码：

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
bool compare(int A, int B) {return A < B;
}
int minNum(int a, int b, int c) {int vec[3];vec[0] = a;vec[1] = b;vec[2] = c;sort(vec, vec + 3, compare);return vec[0];
}
const int N = 0x3f3f3f3f;
int main() {int dp[N];int n; cin >> n;dp[0] = 0;dp[1] = 1;dp[2] = 2;dp[3] = 3;dp[4] = 4;dp[5] = 1;dp[6] = 2;dp[7] = 3;dp[8] = 4;dp[9] = 5;dp[10] = 2;dp[11] = 1;if (n <= 11) {cout << dp[n] << endl;}else {for (int i = 12; i <= n; i++) {dp[i] = minNum(dp[i - 1], dp[i - 5], dp[i - 11]) + 1;}}cout << dp[n] << endl;return 0;
}

建立dp数组；

观察，递推公式可以;

                dp[i] = min(dp[i - 1], dp[i - 5], dp[i - 11]) + 1;

                可得；最终结果

dp[i], 为到达某钱时最小的张数

i, 为到达某钱