动态规划之团灭背包问题
原创
1. 01背包问题
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
f[v]=max{f[v],f[v-c[i]]+w[i]}Note: dp数组容量的init都是dp[v+1], 从空开始init
416. 割等和子集
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
- Each of the array element will not exceed 100.
- The array size will not exceed 200.
Example
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].Solution
容量为sum//2的01背包恰好装满问题
1. 时间O(NV)，空间O(NV)
class Solution:
def canPartition(self, nums: List[int]) -> bool:
if len(nums) <= 1: return False
if sum(nums)%2: return False
target = sum(nums)//2
dp = [[False for _ in range(target+1)] for _ in range(len(nums))]
dp[0][nums[0]] = True
for i in range(1, len(nums)):
for j in range(target+1):
if j >= nums[i]: dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
else: dp[i][j] = dp[i-1][j]
return dp[-1][-1]2. 时间O(NV)，空间O(V)
class Solution:
def canPartition(self, nums: List[int]) -> bool:
if len(nums) <= 1: return False
if sum(nums)%2: return False
target = sum(nums)//2
dp = [False for _ in range(target+1)]
if target >= nums[0]: dp[nums[0]] = True
for i in range(1, len(nums)):
for j in range(target, -1, -1):
if j >= nums[i]: dp[j] = dp[j] or dp[j-nums[i]]
else: break
return dp[-1]494. 目标和
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
Example
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.Solution
01背包问题，恰好被放满
f(i,target)=f(i−1,target−nums[i])+f(i−1,target+nums[i])
class Solution:
def findTargetSumWays(self, nums: List[int], S: int) -> int:
di = {0:1}
for i in range(len(nums)):
nex_di = defaultdict(int)
for s,c in di.items():
nex_di[s+nums[i]] += c
nex_di[s-nums[i]] += c
di = nex_di
return di.get(S, 0)2. 完全背包问题
322. 零钱兑换
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1Example 2:
Input: coins = [2], amount = 3
Output: -1Solution
f(amount)=min(f(amount-coins[i])+1)
class Solution:
def coinChange(self, coins, amount: int) -> int:
if not amount: return 0
dp = [float("inf")] * (amount+1)
for c in coins:
if c <= amount: dp[c] = 1
for i in range(1, amount+1):
for c in coins:
if i-c >= 0:
dp[i] = min(dp[i-c]+1, dp[i])
return dp[-1] if dp[-1] != float("inf") else -1377. 组合总和 IV
Combination Sum IV
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example
nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.Solution
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0 for _ in range(target+1)]
dp[0] = 1
for i in range(1, target+1):
for c in nums:
if i-c>=0: dp[i] += dp[i-c]
return dp[-1]3. 二维费用的背包问题
474. 一和零
Suppose you are a dominator of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0s and 1s.
Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.
Example 1:
Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4
Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s,
which are “10,”0001”,”1”,”0”Solution
1. dp[i][v][u] = max(dp[i][v][u], dp[i-1][v-vi][u-ui]+1)
2. dp[v][u] = max(dp[v][u], dp[v-vi][u-ui]+1 )
时间O(mnl)，空间O(mn)
class Solution:
def findMaxForm(self, strs, m: int, n: int) -> int:
if not strs: return 0
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
for s in strs:
c = Counter(s)
for i in range(m, c["0"]-1, -1):
for j in range(n, c["1"]-1, -1):
dp[i][j] = max(dp[i][j], dp[i-c["0"]][j-c["1"]]+1)
return dp[-1][-1]原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。