随想录算法训练营第四十四天|零钱兑换II、377.组合总和Ⅳ

本文主要是介绍随想录算法训练营第四十四天|零钱兑换II、377.组合总和Ⅳ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

零钱兑换II

public class Solution {public int Change(int amount, int[] coins) {int[]dp=new int[amount+1];dp[0]=1;for(int i=0;i<coins.Length;i++){for(int j=coins[i];j<=amount;j++){dp[j]+=dp[j-coins[i]];}}return dp[amount];}
}

背包问题，但是是每个数可以使用多次即完全背包问题，相比起01背包，完全背包既可以先物品在背包也可以先背包再物品，但这道题不考虑组合，相同种类只算一个，所以先物品后背包，状态转移方程采用Dp[j]+=Dp[j-coins[i]]，最终返回结果。

377.组合总和Ⅳ

public class Solution {public int CombinationSum4(int[] nums, int target) {int[] dp=new int[target+1];dp[0]=1;for(int j=0;j<=target;j++){for(int i=0;i<nums.Length;i++){if(j>=nums[i]){dp[j]+=dp[j-nums[i]];}}}return dp[target];}
}

此题需要考虑组合的计数，所以需要采用先背包再物品，其余同上一题。

这篇关于随想录算法训练营第四十四天|零钱兑换II、377.组合总和Ⅳ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---