代码随想录算法训练营第三十六天 | leetcode：零钱兑换 II,组合总和 Ⅳ
0 / 0 / 创建于 11个月前
_zzh 的个人博客
518. 零钱兑换 II
解题方法
思路：本题物品就是硬币coins,与之前背包问题不一样的是，背包物品可以无限使用，还记得之前01背包一维数组那里强调过，内层循环背包时候：需要倒叙循环，就是为了避免同一个物品重复使用。这不就巧了，这里刚好可以重复使用。而这样的背包问题被称为完全背包问题。
- dp数组的含义：dp[j]：凑成总金额j的货币组合数为dp[j]
- 确定递推公式：与目标和一样，这里是求装满背包一共有多少种方式，而不是求最大价值。
所以递推公式与目标和一样：dp[j] += dp[j-coins[i]];- 初始化dp数组：除了dp[0]=1,其余都初始化为0。
- 遍历顺序：外层为物品（从小到大），内层为背包（从小到大）。
- 注意题目描述中是凑成总金额的硬币组合数，组合不强调元素之间的顺序，排列强调元素之间的顺序。
code
class Solution {
/**
* @param Integer $amount
* @param Integer[] $coins
* @return Integer
*/
function change($amount, $coins) {
//dp[j] = 总金额为j时，有dp[j]种方法可以凑成j
//dp[j] += dp[j-coin[i]];
$dp[0] = 1;
for($i = 0; $i < count($coins); $i++){
for($j = $coins[$i]; $j <= $amount; $j++){
$dp[$j] += $dp[$j-$coins[$i]];
}
}
return $dp[$amount];
}
}复杂度
时间复杂度
O(mn)，其中 m 是amount，n 是 coins 的长度
空间复杂度
O(m)
377. 组合总和 Ⅳ
解题方法
思路：与上一题零钱兑换思路一样，都是完全背包类型的题目，不同的点在于，上一题强调是组合，这一题强调的是排列。不要被组合这个词蒙蔽的双眼
- dp数组的含义：dp[j]：当target为j时，在nums数组中可以组成不同的组合数为d[j]
- 确定递推公式：同样这里是求装满背包一共有多少种方式。
所以递推公式：dp[j] += dp[j-nums[i]];- 初始化dp数组：除了dp[0]=1,其余都初始化为0。
- 遍历顺序：与上一题不同，这一题求排列，需要先遍历背包，再遍历物品。如果先遍历物品则，递推公式$j-$nums[$i]会有负数情况，导致排列数缺失的情况。
code
class Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer
*/
function combinationSum4($nums, $target) {
for($j = 0; $j <= $target; $j++){
//$dp[$j] = 0;
$dp1[$j] = 0;
}
//$dp[0] = 1;
$dp1[0] = 1;
// for($i = 0; $i < count($nums); $i++){
// for($j = 0; $j <= $target; $j++){
// //如果先遍历物品则，递推公式$j-$nums[$i]会有负数情况，导致累计数会少
// if ($j >= $nums[$i]){
// $dp[$j] += $dp[$j-$nums[$i]];
// }
// }
// }
// print_r($dp);
for($j = 1; $j <= $target; $j++){
for($i = 0; $i < count($nums); $i++){
if ($j >= $nums[$i]){
$dp1[$j] += $dp1[$j-$nums[$i]];
}
}
}
//print_r($dp1);
return $dp1[$target];
}
}复杂度
时间复杂度
O(target * n)，其中 n 为 nums 的长度
空间复杂度
O(target)
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号