零钱兑换是很经典的题目,今天解题时却出现一些问题,记录一下
首先想到的是广度优先搜索,用queue实现
int coinChange(vector<int>& coins, int amount) {
queue<vector<int>> nums;
vector<int> passed;//记录已经搜索过的金额,再次遍历到可直接跳过
nums.push(vector<int>(coins.size(),0));//插入初始数量,即全是0
int answer=-1;
for(;nums.size()>0;){
answer++;
int queue_num=nums.size();//存储这一轮所有组合的size
for(int i=0;i<queue_num;i++){
int sum=0;
vector<int> temp=nums.front();
//取出第一个数量组合
for(int j=0;j<temp.size();j++){
sum+=coins[j]*temp[j];//计算总和
}
for(auto k:passed){//如果已经搜索过这个sum就跳过
if(k==sum)
goto here;//goto跳出循环,某些教材写着不要用goto,其实大可不必这么绝对
}
passed.push_back(sum);//没有搜索过该sum就插入
if(sum==amount)
return answer;
if(sum<amount){
for(int j=0;j<temp.size();j++){
temp[j]++;
nums.push(temp);
temp[j]--;//记得恢复原样
}
}
here:nums.pop();//把队头弹出
}
}
return -1;
}
这么写执行起来没问题,该优化的也优化了,但提交还是超时,后来一想还是没看清题,只要求返回次数,并不要求返回具体的组合,相当于我们把题做复杂了。这题广度优先搜索只用记录sum,不用记录组合,这样就能简化很多。
int coinChange(vector<int>& coins, int amount) {
if(amount == 0)
return 0;
queue<int> sum;
int answer=-1;
vector<int> pass;
sum.push(0);
while(sum.size()>0){
answer++;
int size0=sum.size();
for(int i=0;i<size0;i++){
for(auto j:pass){
if(j==sum.front())
goto here;
}
pass.push_back(sum.front());
if(sum.front()==amount)
return answer;
else{
for(auto j:coins){
if(sum.front()<=amount-j)
sum.push(sum.front()+j);
}
}
here:sum.pop();
}
}
return -1;
}
这样写还是超时,换成自顶向下也不行,看来是优化的方法草率了,换做使用动态规划的思想建立数组记录重复值来进一步优化。
public:
int coinChange(vector<int>& coins, int amount) {
pass.resize(amount);
return find(coins,amount);
}
vector<int> pass;
int find(vector<int>& coins, int am){
if(am==0)
return 0;
if(am<0)
return -1;
if(pass[am-1]!=0)
return pass[am-1];
int min0=INT_MAX;
for(auto i:coins){
int res=find(coins,am-i);
if(res>=0&&res<min0){
min0=res+1;
}
}
pass[am-1]=min0==INT_MAX?-1:min0;
return(pass[am-1]);
}
或者直接动态规划
int coinChange(vector<int>& coins, int amount) {
int Max = amount + 1;
vector<int> dp(amount + 1, Max);
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (int j = 0; j < (int)coins.size(); ++j) {
if (coins[j] <= i) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
Comments NOTHING