首页 > 代码库 > careercup-递归和动态规划 9.8
careercup-递归和动态规划 9.8
9.8 给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码就是n分有几种表示法。
解法：
使用回溯法进行解决，实际上就是一个类似枚举的过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
C++实现代码：
#include<vector>#include<iostream>using namespace std;void helper(vector<int> &denom,int target,vector<int> &path,vector<vector<int> > &res){ if(target<0) return; if(target==0) { res.push_back(path); return; } int i; for(i=0;i<(int)denom.size();i++) { path.push_back(denom[i]); helper(denom,target-denom[i],path,res); path.pop_back(); }}vector<vector<int> > makeChange(vector<int> &denom,int target){ if(denom.empty()) return vector<vector<int> >(); vector<vector<int> > res; vector<int> path; helper(denom,target,path,res); return res;}int main(){ vector<int> vec={1,2,3}; vector<vector<int> > res=makeChange(vec,5); for(auto a:res) { for(auto t:a) cout<<t<<" "; cout<<endl; }}
运行结果：
其中存在重复的，譬如：1 1 2 1 和 2 1 1 1。虽然顺序不一样，但是表示的同样的划分。
需要去重。
#include<iostream>using namespace std;int makeChange(int n,int denom){ int next_denom=0; switch(denom) { case 25: next_denom=10; break; case 10: next_denom=5; break; case 5: next_denom=1; break; case 1: return 1; } int i; int way=0; for(i=0;n-i*denom>=0;i++) { way+=makeChange(n-i*denom,next_denom); } return way;}int main(){ cout<<makeChange(100,25)<<endl;}
careercup-递归和动态规划 9.8
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。