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, 为到达某钱