江西的赣州网站建设,花桥网站建设,网站建设销售要懂什么,橙色的网站问题来源
这是Hackerrank上的一个比较有意思的问题#xff0c;详见下面的链接#xff1a; https://www.hackerrank.com/challenges/ctci-coin-change
问题简述
给定m个不同面额的硬币#xff0c;C{c0, c1, c2…cm-1}#xff0c;找到共有几种不同的组合可以使得数额为n的…问题来源
这是Hackerrank上的一个比较有意思的问题详见下面的链接 https://www.hackerrank.com/challenges/ctci-coin-change
问题简述
给定m个不同面额的硬币C{c0, c1, c2…cm-1}找到共有几种不同的组合可以使得数额为n的钱换成等额的硬币每种硬币可以重复使用。 比如给定m3C{2,1,3}n4那么共有4种不同的组合可以换算硬币
{1,1,1,1}{1,1,2}{2,2}{1,3}
解决方案
基本思路是从硬币coins的角度出发考虑coins[0]仅使用1次的情况下有几种组合coins[0]仅使用2次的情况下有几种组合依次类推直到 (n - coins[0] * 使用次数) 0 则终止而每个 (n - coins[0]) 下又可以递归 (n - coins[0] - coins[1]) 的情况直到考虑完所有的硬币。 这样说可能还是没有说清楚下面以m3C{1,2,3}n4为例用图来说明一下建议结合程序一起看。
图1coin Change不完整递归图上图没有画出完整的递归过程有点麻烦~偷了个懒不过把能得出结果的几条路径都描绘出来了。其中recursion(money, index)中money指的是还没有进行兑换的钱index指的是要用哪个coin去兑换比如这里的0指的是coins[0]11指的是coins[1]22指的是coins[2]33是不存在的这也是程序的终止条件之一。 注意到再递归的过程中有重叠子问题我用紫色标注出了其中一个这就可以用动态规划的思想来解决了创建一块空间来存储已经算过的结果就可以了。 # 程序代码 好了下面直接上程序了结合图看好理解~
#include iostream
#include unordered_map
#include string
#include vectorusing namespace std;long long recursion(vectorint coins, int money, int index, unordered_mapstring, int memo){//终止条件2个if (0 money)return 1;if (index coins.size() || money 0)return 0;string key to_string(money) , to_string(index);//如果记录中有的话就直接返回就好了if (memo.find(key) ! memo.end())return memo[key];long long res 0;int remaining money;while(remaining 0){res recursion(coins, remaining, index 1, memo);remaining - coins[index];}//记录一下memo[key] res;return res;
}long long make_change(vectorint coins, int money) {//用哈希表来记录 剩下的钱-用的硬币:换硬币的组合数unordered_mapstring, int memo;long long res recursion(coins, money, 0, memo);return res;
}int main(){int n;int m;cin n m;vectorint coins(m);for(int coins_i 0;coins_i m;coins_i){cin coins[coins_i];}cout make_change(coins, n) endl;return 0;
}Sample Input
10 4
2 5 3 6Sample Output
5真正的DP
上面的那段代码是以自顶向下的方式来解决问题的思路比较清晰而真正的动态规划是自底向上的思路其实也差不多下面给出代码~
long long make_change(vectorint coins, int money) {vectorlong long memo(money 1, 0);memo[0] 1;for (int i 0; i coins.size(); i){for (int j coins[i]; j money; j){memo[j] memo[j - coins[i]];}}return memo[money];
}补充——硬币不能重复使用
如果每种硬币不能重复使用的话又该怎么办呢这只需要再程序上做一些小的改动就可以了真的是非常神奇~ 要细细体会一下~
long long make_change(vectorint coins, int money) {vectorlong long memo(money 1, 0);memo[0] 1;for (int i 0; i coins.size(); i){//改动处由从前往后改成了从后往前略去了重复的情况for (int j money; j coins[i]; j--){memo[j] memo[j - coins[i]];}}return memo[money];
}补充2——不同顺序表示不同组合
然后再来变一变如果每种硬币可以使用无限多次但是不同的顺序表示不同的组合那么又有多少种组合呢 比如
coins [1, 2, 3]
money 4可能的组合情况有
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)注意不同的顺序序列表示不同的组合~所以结果是7。这种情况下的代码是
long long make_change(vectorint coins, int money) {vectorlong long memo(money 1, 0);memo[0] 1;//改变了里外循环的顺序for (int i 1; i money; i){for (int j 0; j coins.size(); j){if (i - coins[j] 0)memo[i] memo[i - coins[j]];}}return memo[money];
}要仔细体会一下三种情况下的区别和代码微妙的变化~
结束语
动态规划的代码量其实不大但是思维量还是挺大的要写正确还是要折腾挺久的~ 本人是初学者如有错误还请指正~
