【TOJ 3206】 Dairy Queen【DP】

题目大意：给你几种价值的钱币，问能有几种组合方式可以组成所给的钱数（每种钱币假设有无限多个）

题解：简单的背包问题 状态以及转移方程见代码注释

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int dp[302], ans[302];//dp[i]表示钱数到达i的方法个数；int n, c[10], cnt;//利用动态规划的思想来解题;int main(){int j, i, k, tem;while (scanf ("%d%d", &n, &cnt) != EOF){memset (dp, 0, sizeof (dp));memset (ans, 0, sizeof (ans));for (i = 0;i < cnt;i++) scanf ("%d", &c[i]);for (i = 0;i <= n;i += c[0]) ans[i] = 1;for (i = 1;i < cnt;i++){for (j = 0;j <= n;j++){for (k = 0;k + j <= n;k += c[i])dp[k + j] += ans[j];}for (j = 0;j <= n;j++) ans[j] = dp[j], dp[j] = 0;//每一次循环后都要重新赋值，避免重复; }printf ("%d\n", ans[n]);}}

如果觉得《【TOJ 3206】 Dairy Queen【DP】》对你有帮助，请点赞、收藏，并留下你的观点哦！