做新媒体的小说网站,网站开发流程前端,html5网站模板 医院,网站设计和建设ppt目录1、题目2、思路分析3、参考链接1、题目
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额#xff0c;返回 -1。
你可以认为每种硬币的数量是无限的。 提示#xff1a; 1 … 目录1、题目2、思路分析3、参考链接 1、题目
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回 -1。
你可以认为每种硬币的数量是无限的。 提示 1 coins.length 12 1 coins[i] 231 - 1 0 amount 104 2、思路分析
这一题和leetcode 39. 组合总和 思考分析有点像不过要求不同。 39题要求的是所有解的集合而这一题求的是最优解。 所以直接套用39回溯思路然后从子解中找到最小的即可貌似也是能做的不过会超时。。。
class Solution {
public:int left_sum;int min_coin_nums;int coin_nums;void backtracking(vectorint coins,int startindex){ if(left_sum 0) return;if(left_sum 0){if(min_coin_nums0) min_coin_numscoin_nums;else min_coin_numsmin(min_coin_nums,coin_nums);return;}for(int istartindex;icoins.size();i){if(left_sum-coins[i]0) break;//处理结点coin_nums;left_sum-coins[i];//递归,探索下一层backtracking(coins,i); //递归//回溯撤销处理结果left_sumcoins[i];coin_nums--;}}int coinChange(vectorint coins, int amount) {min_coin_nums0;coin_nums0;left_sumamount;//排序加速剪枝sort(coins.begin(),coins.end());backtracking(coins,0);if((min_coin_nums 0 amount 0)||(min_coin_nums ! 0)) return min_coin_nums;return -1;}
};其实这一题是一道动态规划题 如果想求amount 11时的最少硬币数(原问题)如果知道amout 10的最少硬币数(子问题)你只需要把子问题的答案加一(再选一枚1元的硬币)因为硬币的数量是没有限制的当然也可能是amout 6的最少硬币数加上一个面额为5的硬币。这时候就需要取最少的硬币数了。 子问题之间是相互独立的。 1、分析最优子结构: 凑成面值为 11 的最少硬币个数可以由以下三者的最小值得到
凑成面值为 10 的最少硬币个数 面值为 1 的这一枚硬币 凑成面值为 9 的最少硬币个数 面值为 2 的这一枚硬币 凑成面值为 6 的最少硬币个数 面值为 5 的这一枚硬币。 dp[11] min (dp[10] 1, dp[9] 1, dp[6] 1)
2、确定【DP状态】 dp[i] 凑齐总价值 i 需要的最少硬币个数 3、确定状态转移方程
for(int i 0;i coins.size();i)
{if (coin[i] amount)dp[amount] min(1 dp[amount - coin[i]]) }需要注意的地方 单枚硬币的面值首先要小于等于 当前要凑出来的面值。
class Solution {
public:int coinChange(vectorint coins, int amount) {int n coins.size();//对dp数组中每个值先赋一个不可能的值因为要比较的是最小值这个不可能的值就得赋值成为一个最大值这里只需要比总金额大就行了表示凑不出来//dp[i] 凑齐总价值 i 需要的最少硬币个数vectorint dp(amount 1,amount1);//凑总金额为0不需要硬币dp[0] 0;//从0到amount计算凑齐总价值 i 需要的最少硬币个数for(int i 0;i amount;i){//从0到coins.size()遍历每个面额的硬币for(int j 0;j n;j){//总价值必须比该硬币面额大//并且dp[i - coins[j]]必须被赋过值也就是说必须有个方案要能够凑出来这样才能进行下一步推导if(i - coins[j] 0 dp[i - coins[j]] ! amount1){//如果满足这个条件那么dp[i]就是dp[i]和当前方案中的最小值因为dp[i]可能被多次赋值我们取的是最优值dp[i] min(dp[i],1 dp[i - coins[j]]);}}}//dp[amount]没有没赋值说明没有组合方案所以应该返回-1if(dp[amount] amount1){return -1;}return dp[amount];}};时间复杂度O(N \times amount)O(N×amount)这里 NN 是可选硬币的种类数amountamount 是题目输入的面值 空间复杂度O(amount)O(amount)状态数组的大小为 amountamount。 由于dp数组是自底向上求解的所以过程中不会出现重叠子问题 需要注意的地方 1、数组初始化把初值amount1换成Integer.MAX_VALUE为什么就不行了 如果初值赋值为正无穷dp[i - coin] 1 可能会发生整型溢出。 2、循环的判断条件if (i - coin 0 dp[i - coin] ! amount 1)为什么要判断 dp[i - coin] ! amount 1呢 amount 1 在这里表示的是当前状态表示的金额不能被候选硬币的和表示。 去掉dp[i-coin] ! amount 1 这个判断条件也是可以的 因为若是 dp[i-coin] amount 1 在下一步 dp[i] Math.min(dp[i], 1 dp[i - coin]) 也会将amount11这个值过滤掉的即amount 1仍然是无效的。 因为数组中的有效值不会超过amount1就算有1块钱的硬币最大值也就是amount因此在取两个数的最小值时已经自动将amount1这个值过滤掉了。 3、参考链接
动态规划、完全背包、BFS包含完全背包问题公式推导 labuladong的公众号文章
