首页 > 代码库 > UVA674- Coin Change
UVA674- Coin Change
题意:用所给的硬币面值构成所需的面值
思路:因为所用硬币数量不限,所以很容易想到完全背包。
递推:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 10005; int n; int coin[] = {1, 5, 10, 25, 50}; long long d[MAXN]; void dp() { memset(d, 0, sizeof(d)); d[0] = 1; for (int i = 0; i < 5; i++) for (int j = coin[i]; j < MAXN; j++) d[j] += d[j - coin[i]]; } int main() { dp(); while (scanf("%d", &n) != EOF) { printf("%lld\n", d[n]); } return 0; }
记忆化搜索:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 10005; int n; int coin[] = {1, 5, 10, 25, 50}; long long d[MAXN][6]; void init() { memset(d, -1, sizeof(d)); for (int i = 0; i < 5; i++) d[0][i] = 1; } long long dp(int s, int m) { if (d[s][m] != -1) return d[s][m]; d[s][m] = 0; for (int i = m; i < 5 && s >= coin[i]; i++) d[s][m] += dp(s - coin[i], i); return d[s][m]; } int main() { init(); while (scanf("%d", &n) != EOF) { long long ans = dp(n, 0); printf("%lld\n", ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。