拼凑钱币-动态规划

拼凑钱币

       给你六种面额 1、5、10、20、50、100 元的纸币，假设每种币值的数量都足够多，编写程序求组成N元（N为0~10000的非负整数）的不同组合的个数。

       coins = {1, 5, 10, 20, 50, 100};

       假设dp[i][j]表示前i种纸币构成值为j的所有组合总数，则对于第i种纸币来说，有三种种情况：

(1) 当 coins[i] > j 时，无法构成值 j，此时dp[i][j] = dp[i-1][j]； 

(2) 当 coins[i] = j 时，dp[i][j] = dp[i-1][j-coins[i]]+1;（coins[i] = j 时，coins此种纸币即可构成值 j）

(2) 当 coins[i] < j 时，对于第 i 种纸币来说有两种选择：用或不用；

       a. 不用：dp[i][j] = opt[i-1][j]；前 i 种纸币可构成 j 的最大组合数即是前 ( i - 1) 种纸币可构成 j 的最大组合数；

       b. 用： dp[i][j] = dp[i][j-coins[i]]；前 i 种纸币可构成 j 的最大组合数即是前( i - 1 )种纸币构成值为(j - coins[i])的最大组合数。

综上，状态转换方程如下：

代码如下：

#include <iostream>
#include <vector>using namespace std;int main()
{int n;cin >> n;vector<int> coins(n, 0);for (auto &m : coins)cin >> m;int sum;while (cin >> sum){vector<vector<long long>> dp(n, vector<long long>(sum + 1, 0));for (int j = 1; j <= sum; j++)dp[0][j] = 1;for (int i = 1; i < n; i++){for (int j = 1; j <= sum; j++){if (coins[i] > j)dp[i][j] = dp[i - 1][j];else if (coins[i] < j)dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];elsedp[i][j] = dp[i - 1][j] + 1;}}cout << dp[n - 1][sum] << endl;}return 0;
}

上述方法的时间复杂度和空间复杂度均为O(n*sum)，其中空间复杂度是可以优化到O(sum)的。状态方程如下：

令dp[0] = 1，上式可以简化为：

代码如下：

#include <iostream>
#include <vector>using namespace std;int main()
{int n;cin >> n;vector<int> coins(n, 0);for (auto &m : coins)cin >> m;int sum;while (cin >> sum){vector<long long> dp(sum + 1, 1);  //  dp[j]初始值全为1（包括dp[0]也为1）for (int i = 1; i < n; i++){for (int j = 1; j <= sum; j++){if (j >= coins[i])dp[j] += dp[j - coins[i]];  //  j<coins[i]时，dp[j]不变，无需操作}}cout << dp[sum] << endl;}return 0;
}

零钱兑换

       给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

#include<iostream>
#include<vector>
#include<algorithm>using namespace std;int main()
{int n;cin >> n;vector<int> coins(n, 0);for (auto & m: coins)cin >> m;int sum;while (cin >> sum){vector<vector<int>> dp(n, vector<int>(sum + 1, INT_MAX - 1));for (int i = 0; i < n; i++)dp[i][0] = 0;for (int j = 1; j <= sum; j++){if (j >= coins[0])dp[0][j] = min(dp[0][j], dp[0][j - coins[0]] + 1);}for (int i = 1; i < n; i++){for (int j = 1; j <= sum; j++){if (j >= coins[i])dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i]] + 1);elsedp[i][j] = dp[i - 1][j];}}if (dp[n - 1][sum] == INT_MAX-1)cout << -1 << endl;elsecout << dp[n - 1][sum] << endl;}return 0;
}

#include<iostream>
#include<vector>
#include<algorithm>using namespace std;int main()
{int n;cin >> n;vector<int> coins(n, 0);for (auto & m : coins)cin >> m;int sum;while (cin >> sum){vector<int> dp(sum + 1, INT_MAX - 1);dp[0] = 0;for (int i = 0; i < n; i++){for (int j = 1; j <= sum; j++){if (j >= coins[i])dp[j] = min(dp[j], dp[j - coins[i]] + 1);}}if (dp[sum] == INT_MAX - 1)cout << -1 << endl;elsecout << dp[sum] << endl;}return 0;
}