动规part 05

LC 518.零钱兑换II

本题是完全背包求组合中的应用

tips:

求组和，先遍历物品，再遍历背包；求排列，先遍历背包，再遍历物品。

将本题和LC 494 对比着看，加深印象。

class Solution:def change(self, amount: int, coins: List[int]) -> int:dp = [0] * 5001dp[0] = 1for i in range(len(coins)):for j in range(coins[i] , amount + 1):dp[j] += dp[j-coins[i]]return dp[amount]

Java版本

class Solution {public int change(int amount, int[] coins) {int[] dp =new int [5001];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];}
}

LC 377. 组合总和 Ⅳ

本题是完全背包求排列的应用，与之前的几个题类似。但是求排列是先遍历背包，再遍历物品！

class Solution:def combinationSum4(self, nums: List[int], target: int) -> int:dp = [0] * 1001dp[0] = 1for j in range(0, target + 1):for i in range(0,len(nums)):dp[j] += dp[j-nums[i]]return dp[target]

JAVA版

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] >= 0){dp[j] += dp[j - nums[i]];}}}return dp[target];}
}

注意，java代码必须先判断 j - nums[i] 是否大于等于零，因为java不像python那样，支持索引为负数。

实际上，python版本的代码也应该判断，因为 j - nums[i]表示的是还未放入物品 i 时，为了等会放进物品 i ，预留nums[ i ]的容量后 ，背包还剩多少容量。负数没有意义，至少得是0.

LC 322. 零钱兑换

本题递推公式需要自己推一遍

容易想到使用数组dp[ j ]代表容量为 j (要凑足j这么多的钱)的背包，最少的硬币数为dp[j]。对于硬币 i ，面值为coins[i] , 没放入它的时候 ，要凑足j - coins[i]这么多钱，最少的硬币数为dp[j - coins[i]]，那么要凑足j这么多钱，只需要dp[ j - coins[i]] + 1枚硬币即可！

如何更新dp数组？

我们需要取最小值，也就是 dp = min(dp , dp[ j - coins[i]] + 1) ，这就要求在初始化时，除了dp[0] = 0外，其他位置的元素能多大就多大，以保证数组的更新。

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:if amount == 0: return 0dp = [float('inf')] * (amount + 1)dp[0] = 0for i in range(len(coins)):for j in range(coins[i] , amount + 1):dp[j] = min(dp[j] , dp[j - coins[i]] + 1)if dp[amount] == float('inf'): return -1return dp[amount]

JAVA版

class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];for(int i = 1 ; i < dp.length ; i++){dp[i] = Integer.MAX_VALUE;}for(int i = 0 ; i < coins.length ; i ++){for(int j = coins[i] ; j <= amount ; j ++){if(dp[j - coins[i]] != Integer.MAX_VALUE){dp[j] = Math.min(dp[j] , dp[j-coins[i]] + 1);}}}if(dp[dp.length - 1] == Integer.MAX_VALUE){return -1;}else{return dp[amount];}}
}

tips:

之前没加下面这行代码，导致运行结果出现了一个诡异的数字-2147483648，

这再次体现了JAVA与python的不同，在python版本中，我没有判断下面这行代码，也正确运行得出结果了，这是因为python里的min(dp[j] , dp[j-nums[i]] + 1)，若两者都是inf，仍然会保持inf。

而java中，我们设置的是Integer.MAX_VALUE,代表整数中的最大值，此时我们给他 + 1，会导致整数溢出，这在Java中会导致一个负值，这个负值会立即被识别为小于 Integer.MAX_VALUE，所以返回了这个诡异的数字。

因此严谨地考虑，python和java版本中，都应该加入下面这行代码，这表示在构成dp[j] 之前， 有没有dp[ j - coins[ i ]] 这种组合 ， 若没有，则不执行更新。

if(dp[j - coins[i]] != Integer.MAX_VALUE)