Leetcode刷题(11) 背包问题系列(动态规划)

416. 分割等和子集

参考labuladong的经典动态规划：0-1 背包问题，经典动态规划：0-1背包问题的变体

# 0-1背包问题的变体 class Solution(object): def canPartition(self, nums): """ :type nums: List[int] :rtype: bool """ size = len(nums) Sum = 0 # 计算总数和 for num in nums: Sum += num # 如果是奇数的话则nums无法被分割成两个等和的子集 if Sum % 2 != 0: return False # 取得一半作为背包的容量 Sum = Sum / 2 dp = [[False] * (Sum + 1) for _ in range(size + 1)] # 如果背包的容量为0的时候, 肯定可以装满 for i in range(size + 1): dp[i][0] = True for i in range(1, size + 1): for w in range(1, Sum + 1): # 当前背包的容量不够, 第i个物品无法装入 if w - nums[i-1] < 0: dp[i][w] = dp[i-1][w] else: # 选择不装还是装, 只要一个符合就行 dp[i][w] = dp[i-1][w] or dp[i-1][w-nums[i-1]] return dp[size][Sum]

518. 零钱兑换 II

具体方法参考labuladong的经典动态规划：完全背包问题

class Solution(object): def change(self, amount, coins): """ :type amount: int :type coins: List[int] :rtype: int """ num_coins = len(coins) # base case dp = [[0] * (amount + 1) for _ in range(num_coins + 1)] for i in range(num_coins + 1): dp[i][0] = 1 for i in range(1, num_coins + 1): for j in range(1, amount + 1): if j - coins[i-1] < 0: # 放不下, 那第i种硬币就不能用 dp[i][j] = dp[i-1][j] else: # 不用第i种硬币 + 用第i种硬币，注意这里是dp[i][j-coins[i-1]]不是dp[i-1][j-coins[i-1]]，因为是完全背包问题，每种硬币的个数无限 dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]] return dp[num_coins][amount]