算法日记29：leetcode322零钱兑换（DFS-＞记忆化搜索-＞DP)

一、题目：

二、解题思路

0）其实，题目一眼就可以看出是完全背包模型，但我们仍然可以用公式来推导

1）动态规划解题思路

• 总结：（原问题的答案=去掉最后一步的子问题答案+？）即可得出递推公式

2）具体分析

• 接着，往下一直划分直到$amount=0$，即为边界

三、DFS实现：

1、思路解析

1）因为没有对硬币数量/顺序的限制，因此只需要遍历选择了某个银币，使得金额从$amount->0$即可

2）注意边界：也就是当$amount=0$或$amount<0$的情况

• $amount=0$：
  • if(amount==0) return 0;//表示凑完了，此时表示到达了递归终点，直接逐层return 0即可
• $amount<0$：
  • 法一：if(amount<0) return 1e9;//表示此时不合法 ，此时不合法，return一个极大值即可
  • 法二：if(amount>=coins[i]) //当前剩余金额>=当前枚举到的硬币值，在递归函数前加一个if语句判断，使得符合条件

2、代码实现

//1、重述问题：用最小的硬币数凑出amount,求硬币数
//2、找出最后一步：选择了某个硬币x，使得金额变成了amount
//3、去掉最后一步，问题变成了什么？
//-->用最小的硬币数，凑出：amount-coins[x]
//-->原问题答案=(用最少的硬币数，凑出(amount-coins[x]))+1
class Solution {
public:int dfs(vector<int>& coins, int amount){if(amount==0) return 0; //表示凑完了//if(amount<0) return 1e9;//表示此时不合法int ans=1e9;for(int i=0;i<coins.size();i++) //选择了某个银币，使得金额变成了amount{if(amount>=coins[i]) //当当前剩余金额>=当前枚举到的硬币值ans=min(ans,dfs(coins,amount-coins[i])+1);}return ans;}int coinChange(vector<int>& coins, int amount) {return dfs(coins,amount)==1e9? -1 : dfs(coins,amount);}
};

四、记忆化搜索：

1、思路解析

1）在$DFS$(递归)中，存在着大量的重复计算，因此我们可以使用记忆化搜索来进行优化

2、代码实现

//1、重述问题：用最小的硬币数凑出amount,求硬币数
//2、找出最后一步：选择了某个硬币x，使得金额变成了amount
//3、去掉最后一步，问题变成了什么？
//-->用最小的硬币数，凑出：amount-coins[x]
//-->原问题答案=(用最少的硬币数，凑出(amount-coins[x]))+1
class Solution {
public:int mem[10007];int dfs(vector<int>& coins, int amount){if(mem[amount]) return mem[amount];if(amount==0) return 0; //表示凑完了int ans=1e9;for(int i=0;i<coins.size();i++) //选择了某个银币，使得金额变成了amount{if(amount>=coins[i]) //当当前剩余金额>当前枚举到的硬币值ans=min(ans,dfs(coins,amount-coins[i])+1);}mem[amount]=ans;return mem[amount];}int coinChange(vector<int>& coins, int amount) {return dfs(coins,amount)==1e9? -1 : dfs(coins,amount);}
};

五、动态规划

1、思路解析

1）在递归中，我们可以发现限制边界的条件有

• 当前枚举到了第几枚硬币
• 当前剩余的金额

2）因此，我们应该循环遍历这两个变量，并且改写：DFS递归方程->状态转移方程

	int coinChange(vector<int>& coins, int amount) {//return dfs(coins,amount)==1e9? -1 : dfs(coins,amount);int n=coins.size();int dp[10007];memset(dp,0x3f,sizeof(dp));dp[0]=0;for(int i=0;i<n;i++)    //枚举选择哪个硬币{for(int j=0;j<=amount;j++)  //枚举金额{if(j>=coins[i]) dp[j]=min(dp[j],dp[j-coins[i]]+1);}}return dp[amount]>=0x3f3f3f3f ? -1 : dp[amount];}

2、代码实现

//1、重述问题：用最小的硬币数凑出amount,求硬币数
//2、找出最后一步：选择了某个硬币x，使得金额变成了amount
//3、去掉最后一步，问题变成了什么？
//-->用最小的硬币数，凑出：amount-coins[x]
//-->原问题答案=(用最少的硬币数，凑出(amount-coins[x]))+1
class Solution {
public:// int mem[10007];// int dfs(vector<int>& coins, int amount)// {//     if(mem[amount]) return mem[amount];//     if(amount==0) return 0; //表示凑完了//     int ans=1e9;//     for(int i=0;i<coins.size();i++) //选择了某个银币，使得金额变成了amount//     {//         if(amount>=coins[i]) //当当前剩余金额>当前枚举到的硬币值//         ans=min(ans,dfs(coins,amount-coins[i])+1);//     }//     mem[amount]=ans;//     return mem[amount];// }int coinChange(vector<int>& coins, int amount) {//return dfs(coins,amount)==1e9? -1 : dfs(coins,amount);int n=coins.size();int dp[10007];memset(dp,0x3f,sizeof(dp));dp[0]=0;for(int i=0;i<n;i++)    //枚举选择哪个硬币{for(int j=0;j<=amount;j++)  //枚举金额{if(j>=coins[i]) dp[j]=min(dp[j],dp[j-coins[i]]+1);}}return dp[amount]>=0x3f3f3f3f ? -1 : dp[amount];}
};