原题链接: leetcode 322. 零钱兑换
注意:
class Solution {
public:
int coinChange(vector<int>& coins, int amount)
{
if (amount == 0) return 0;
queue<int> q;
//设置访问数组标记,判断当前剩余零钱数是否被凑出来过
set<int> visited;
q.push(amount);
//将当前剩余需凑零钱数设置为已访问过
visited.insert(amount);
//当前用了多少硬币来凑零钱
int step = 1;
排序是为了加快广度优先遍历过程中,对硬币面值的遍历,起到剪枝的效果
sort(coins.begin(), coins.end());
while (!q.empty())
{
//获取队列中存储当前层元素个数
int size = q.size();
for (;size>0;size--)
{
//获取当前队列首元素
int head = q.front();
q.pop();
for (auto& coin : coins)
{
int next = head - coin;
if (next == 0)// 只要遇到 0,就找到了一个最短路径
return step;
if(next<0)
// 由于 coins 升序排序,后面的面值会越来越大,剪枝
break;
//图中当前点没有被访问过
if (visited.count(next) == 0)//当前可能性没有被找到过
{
q.push(next);
// 添加到队列的时候,就应该立即设置当前节点为访问过
// 否则还会发生重复访问
visited.insert(next);
}
}
}
//每遍历完当前层元素都表示拿出了一个硬币来凑零钱,如果不明白,可以看一下图
step++;
}
// 进入队列的顶点都出队,都没有看到 0 ,就表示凑不出当前面值
return -1;
}
};
思路:分析最优子结构。根据示例 1:
输入: coins = [1, 2, 5], amount = 11
凑成面值为 11 的最少硬币个数可以由以下三者的最小值得到:
即 dp[11] = min (dp[10] + 1, dp[9] + 1, dp[6] + 1)。
可以直接把问题的问法设计成状态。
//这里还需要比较dp[amount]是因为,举个例子吧!
//如例1:如果当前dp[amount]的值已经再之前的比较中被赋值为了3,此时dp[amount-coins[i]]+1得到的值为4,此时显然还是3最小
//因此这里还需要比较如果当前已经是最小值了,那么就不用更新最小值了
dp[amount] = min(dp[amount], 1 + dp[amount - coins[i]])
注意:
再次强调:新状态的值要参考的值以前计算出来的「有效」状态值。因此,不妨先假设凑不出来,因为求的是小,所以设置一个不可能的数。
参考代码 1: 注意:要求的是「恰好凑出面值」,所以初始化的时候需要赋值为一个不可能的值:amount + 1。只有在有「正常值」的时候,「状态转移」才可以正常发生。
class Solution {
public:
int coinChange(vector<int>& coins, int amount)
{
//这里dp含义是:凑齐总价值 i 需要的最少硬币个数;
int* dp = new int[amount+1];
// 因为我们要挨个求出凑出0元到amount元分别每一个需要的最少硬币数量,
//因此一开始假设最少需要硬币数量为一个不可能的最大值
for (int i = 0; i < amount+1; ++i)
dp[i] = amount + 1;
//凑出总价值为0,所需要的硬币数为0---这是最小的子问题,我们可以直接得出
dp[0] = 0;
//下面从最小子问题一层层往上求出最大问题
//这里循环从1开始,表示从凑出1元的子问题开始往上面求
for (int i = 1; i <= amount; ++i)
{
//遍历硬币数组,看能否凑出当前需要的硬币数i
for (int coin : coins)
{
//只能当前硬币的面值比我们需要凑的值小才能选,不然就超了
//选择当前硬币后存在两种可能:
//1.刚好凑出来所需要的硬币数---i-coin==0---dp[i-coin]==dp[0]==0
//2.拿了当前硬币后,还是没凑满所需要的硬币数量---i-coin>0---dp[i-coin] ?
//这里又分了两种情况:
//(1): dp[i- coin] != amount + 1 首先这里i-coin是再选择当前硬币后,剩余带凑的硬币数
//这里剩余带凑的硬币数量不等于amount+1,说明我们在此之前,已经求出了需要凑出i-coin数量硬币的最少需要的硬币数
//那么这里要求凑出当前i数量的硬币数,不就是拿了当前面值为coin的硬币后,加上之前求出凑出i-coin数量硬币的最少需要的硬币数,即dp[i-coin]
//所以最终得到选了当前硬币后最少需要的硬币数----dp[i]=dp[i-coin]+1
//但是凑出dp[i]可能不止一种方法,可能在此之前已经求出一种凑出i的最少数,因此这里需要进行对比,选择所有可能中最小的
//因此最终得到: dp[i] = min(dp[i], dp[i-coin]+1);
//(2): dp[i- coin] == amount + 1
//说明在我们拿了面值为coin硬币后,剩余硬币数为i-coin,按理来说在我们选择了当前硬币后,需要凑出i的最小硬币数应该是:
//dp[i]=dp[i-coin]+1-----但是dp[i-coin],即凑出剩余硬币数i-coin所需要的最少硬币数没有算出来,
//但是注意我们最外层循环已经说了,是从最小的1开始往上直到amount,一层层求出每个所需要的最少硬币数
//既然i-coin比i小,并且dp[i-coin]==amount+1等于最大值初始值,说明现有的硬币种类根本无法凑出i-coin的值
//既然求不出i-coin的所需要的最少硬币数,自然也无法求出当前i所需要的最少硬币数
if (i - coin >= 0 && dp[i- coin] != amount + 1)
{
dp[i] = min(dp[i], dp[i-coin]+1);
}
}
}
//如果经历了上面的循环后,dp[amount] == amount + 1,说明现有硬币种类凑不出amount的值
//例如:我们有硬币5,10,20 --现在要你凑出1元---你给我凑一个试试!!!!
if (dp[amount] == amount + 1)
return -1;
//如果可以凑出,就直接返回最终值即可
return dp[amount];
}
};
「动态规划」是「自底向上」求解。事实上,可以 直接面对问题求解 ,即「自顶向下」,但是这样的问题有 重复子问题,需要缓存已经求解过的答案,这叫 记忆化递归。
参考代码 2: 注意:由于 -1 是一个特殊的、有意义状态值(题目要求不能使用给出硬币面值凑出的时候,返回 -1),因此初值赋值为 -2,表示还未计算出结果。
class Solution {
public:
int coinChange(vector<int>& coins, int amount)
{
int* dp = new int[amount + 1];
//初始值都为-2,表示当前还没结果
fill(dp, dp + amount + 1, -2);
//给硬币面值进行排序,目的是方便递归的时候进行剪枝
sort(coins.begin(), coins.end());
return dfs(coins, dp, amount);
}
int dfs(vector<int>& coins,int*& dp,int amount)
{
int res = INT_MAX;
//说明当前我们要返回最小子问题求解结果---凑出0元钱等于我不要任何硬币
if (amount == 0) return 0;
//凑出amount数量的值,我们已经算出了结果
//-2表示没有算出结果
if (dp[amount] != -2) return dp[amount];
//如果还没算出结果,那么就去给我算!!!
//尝试去拿一次每个面值的硬币,看看拿了之后,加上凑出amount-coin的值需要的最小硬币数是多少
//用res保存拿了其中某个面值的硬币后,得到的最少需要的硬币数
for (int coin : coins)
{
//说明当前硬币面值大于所需要凑出来的值,因为之前对硬币面值数组进行了排序,所以这里可以进行剪枝
//后面的面值比当前的硬币面值还要大,你觉得还有必要试试吗???
if (amount - coin < 0) break;
//获取凑出剩余硬币数所需要的最少硬币数
int subres = dfs(coins, dp, amount-coin);
//如果剩余硬币数凑不出来,那么当前硬币拿了也没用,反正也凑不出来
//那怎么办??? 看看还有没有其他面值硬币好拿呗
if (subres == -1)
continue;
//如果我们得到了剩余硬币数的结果,那么我们需要比较
//因为凑出当前硬币数可能不止一种方法,我们需要选择最小的那种方案
res = min(res, 1 + subres);
}
//如果最终res的值还是无穷大,那么说明当前值凑不出来
//如果不是无穷大,那么res记录的就是当前硬币被凑出所需要的最少硬币数
return dp[amount] = (res == INT_MAX) ? -1 : res;
}
};
为什么是「完全背包」问题:
但是与「完全」背包问题不一样的地方是:
这一点可以认为是:每一个硬币有一个「占用空间」属性,并且值是固定的,固定值为 11;作为「占用空间」而言,考虑的最小化是有意义的。等价于把「完全背包」问题的「体积」和「价值」属性调换了一下。因此,这个问题的背景是「完全背包」问题。
可以使用「完全背包」问题的解题思路(「0-1 背包」问题也是这个思路):
所以在代码里:外层循环先遍历的是硬币面值,内层循环遍历的是面值总和。
这里我先举一个例子:
class Solution {
public:
int coinChange(vector<int>& coins, int amount)
{
//注意:这里dp[i]依旧表示最少需要的硬币数量
//i表示当前钱包的容量---这里只是理解为往钱包里面塞入大小为amount值的钱
int* dp = new int[amount + 1];
//都初始化为最大值,表示还没有计算出结果
fill(dp, dp + amount + 1, amount + 1);
//当钱包可容纳钱的数量为0时,我们不需要往钱包里面放一毛钱!!!
dp[0] = 0;
//遍历当前每个房间---每个房间堆放不同面值的硬币
for (int coin : coins)
{
//钱包的容量至少要为当前面值硬币大小,不然怎么放的下呢?
//钱包容量由最小值coin一直变大到amount,由子问题一层层求解得到大问题
for (int i = coin; i <= amount; ++i)
{
//当前钱包的最少硬币数,是会随着发现不同硬币而做出不同选择而发生改变的
//可能选择后硬币数会更少,也可能会更多
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
if (dp[amount] == amount + 1)
return -1;
return dp[amount];
}
};
int