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
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:
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]
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)
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 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
Solution
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 -1
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]
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 删除。