1049. 最后一块石头的重量 II
- 思路
- example
- 并不是找最优方案，只需要最优的output
- 1 <= stones[i] <= 100
-
把石头分成重量尽量接近的两堆 （+， -）, 这样两者之绝对差就是答案！
- stones = [1, 8, 4]; -1 + 8 - 4 = 3
- 暴力回溯 (麻烦)
- DP
- 1维DP，dp[j]: 重量为j的（-）背包所能背石头的最大重量
- 目标：return (sum_ - dp[target]) - dp[target])
- target = sum_ // 2
- 0-1背包，1D逆序遍历j
- 复杂度. 时间：O(n*sum_), 空间: O(sum_)
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
n = len(stones)
sum_ = sum(stones)
target = sum_ // 2
dp = [0 for _ in range(target+1)]
for i in range(n):
for j in range(target, -1, -1):
if j >= stones[i]:
dp[j] = max(dp[j], dp[j-stones[i]] + stones[i])
return (sum_ - dp[target]) - dp[target]
- 2D
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
n = len(stones)
sum_ = sum(stones)
target = sum_ // 2
dp = [[0 for _ in range(target+1)] for _ in range(n)]
for j in range(target+1):
if j >= stones[0]:
dp[0][j] = stones[0]
for i in range(1, n):
for j in range(target+1):
if j < stones[i]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i]]+stones[i])
return sum_ - 2*dp[-1][target]
494. 目标和
- 思路
- example
- 返回不同 表达式 的数目。
- 暴力回溯
- 数字分为两组：positive (+), negative (-)
positive - negative = target
positive + negative = sum_
positive = (sum_ + target) // 2 (if sum+ target is even)
- 选出(+)子集使得和为positive (integer)
- 0 <= nums[i] <= 1000, -1000 <= target <= 1000
- 0-1背包
- 背包容量：j
- 物品：每个数字最多选一次
- DP (1D): dp[j]: 使得（＋）数组和为ｊ的组合数。
- dp[0] = 1
- 目标：dp[positive]
- 复杂度. 时间：O(n*sum_), 空间: O(sum_)
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
n = len(nums)
sum_ = sum(nums)
if (target + sum_) % 2 != 0:
return 0
else:
positive = (target + sum_) // 2
if positive < 0:
return 0
dp = [0 for _ in range(positive+1)]
dp[0] = 1
for i in range(n):
for j in range(positive, -1, -1):
if j >= nums[i]:
dp[j] += dp[j-nums[i]] # 选与不选两种情况累加
return dp[positive]
- 2D: 初始化比较绕 (没有用“前i个”来处理）
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
n = len(nums)
sum_ = sum(nums)
if (sum_ + target) % 2 != 0:
return 0
positive = (sum_ + target) // 2
if positive < 0: # !!!
return 0
dp = [[0 for _ in range(positive+1)] for _ in range(n)]
dp[0][0] = 1 # !!!
for j in range(positive+1):
if j == nums[0]: # !!!
dp[0][j] += 1 # !!! 累加, 有可能nums[0] == 0
for i in range(1, n):
for j in range(positive+1):
if j < nums[i]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]
print(dp)
return dp[-1][positive]
- 2D, 前i个
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
n = len(nums)
total = sum(nums)
if (total + target) % 2 != 0:
return 0
pos = (total + target) // 2
if pos < 0: #!!!
return 0
dp = [[0 for _ in range(pos+1)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
for j in range(pos+1):
if j < nums[i-1]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]
return dp[n][pos]
- 暴力回溯(dfs)
- memo DFS
TBA
474. 一和零
- 思路
- example
- 0-1背包
- 背包：2个维数（‘0’的个数，‘1’的个数）
- dp[k][i][j]: strs[0], ..., strs[k]里选（最大）子集个数 使得最多含有i个'0', j个‘1’
- 复杂度. 时间：
, 空间:
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
dp = [[[0] * (n+1) for _ in range(m+1)] for _ in range(len(strs))]
zeros, ones = 0, 0
for ch in strs[0]:
if ch == '0':
zeros += 1
else:
ones += 1
for i in range(zeros, m+1):
for j in range(ones, n+1):
dp[0][i][j] = 1
for k in range(1, len(strs)):
zeros, ones = 0, 0
for ch in strs[k]:
if ch == '0':
zeros += 1
else:
ones += 1
for i in range(m+1):
for j in range(n+1):
if i < zeros or j < ones:
dp[k][i][j] = dp[k-1][i][j]
else:
dp[k][i][j] = max(dp[k-1][i][j], dp[k-1][i-zeros][j-ones] + 1)
return dp[len(strs)-1][m][n]
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
K= len(strs)
dp = [[[0 for _ in range(n+1)] for _ in range(m+1)] for _ in range(K)]
zeros, ones = 0, 0
for ch in strs[0]:
if ch == '0':
zeros += 1
else:
ones += 1
for i in range(zeros, m+1):
for j in range(ones, n+1):
dp[0][i][j] = 1
for k in range(1, K):
zeros, ones = 0, 0
for ch in strs[k]:
if ch == '0':
zeros += 1
else:
ones += 1
for i in range(m+1):
for j in range(n+1):
if i < zeros or j < ones:
dp[k][i][j] = dp[k-1][i][j]
else:
dp[k][i][j] = max(dp[k-1][i][j], dp[k-1][i-zeros][j-ones] + 1)
return dp[K-1][m][n]
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
def cal_zeros(s):
cnt = 0
for ch in s:
if ch == '0':
cnt += 1
return cnt
N = len(strs)
dp = [[[0 for _ in range(n+1)] for _ in range(m+1)] for _ in range(N)]
zeros = cal_zeros(strs[0])
ones = len(strs[0]) - zeros
for i in range(m+1):
for j in range(n+1):
if i >= zeros and j >= ones:
dp[0][i][j] = 1
for k in range(1, N):
zeros = cal_zeros(strs[k])
ones = len(strs[k]) - zeros
for i in range(m+1):
for j in range(n+1):
if i < zeros or j < ones:
dp[k][i][j] = dp[k-1][i][j]
else:
dp[k][i][j] = max(dp[k-1][i][j], dp[k-1][i-zeros][j-ones] + 1)
return dp[N-1][m][n]
- 可空间优化: dp[i][j]
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
def count(s):
zeros, ones = 0, 0
for ch in s:
if ch == '0':
zeros += 1
elif ch == '1':
ones += 1
return zeros, ones
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
for k in range(len(strs)):
zeros, ones = count(strs[k])
for i in range(m, -1, -1):
for j in range(n, -1, -1):
if i >= zeros and j >= ones:
dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones] + 1)
return dp[m][n]
- dfs, memo dfs
TBA
