1049.最后一块石头的重量II
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
total = sum(stones)
target = total // 2
dp = [0] * (target + 1)
for stone in stones:
for j in range(target, stone - 1, -1):
dp[j] = max(dp[j], dp[j-stone] + stone)
return total - dp[target] - dp[target]
494. 目标和
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
total = sum(nums)
# 排除边界情况
if abs(target) > total:
return 0
if (total + target) % 2 != 0:
return 0
# 背包
left_num = (total + target) // 2
# dp[j] 代表正数集合为 j 的方法总数为 dp[j]
# 初始化 dp
dp = [0] * (left_num + 1)
dp[0] = 1
for num in nums:
for j in range(left_num, num - 1, -1):
dp[j] += dp[j-num]
return dp[-1]
474.一和零
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
dp = [[0] * (n + 1) for _ in range(m + 1)]
for s in strs:
zero_num = s.count("0")
one_num = s.count("1")
for i in range(m, zero_num - 1, -1):
for j in range(n, one_num - 1, -1):
dp[i][j] = max(dp[i][j], dp[i - zero_num][j - one_num] + 1)
return dp[m][n]