最后一块石头的重量

与分割等和子集类似

思路：尽量分割成两个sum值相近的数组1和2，求其中一个数组为sum(stone)//2时的一种情况

dp[j]:容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]

def lastStoneWeightII(self, stones: List[int]) -> int:
    dp = [0] * 15001
    total_sum = sum(stones)
    target = total_sum // 2

    for stone in stones:  # 遍历物品
        for j in range(target, stone - 1, -1):  # 遍历背包
            dp[j] = max(dp[j], dp[j - stone] + stone)

    return total_sum - dp[target] - dp[target]

目标和

思路：分为全为+号和全为-号的两个数组，add+reduce=target add-reduce=sum(nums)
所以add=(sum(nums)+target)/2

dp[j]:填满j（包括j）这么大容积的包，有dp[j]种方法

 def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total_sum = sum(nums)  # 计算nums的总和
        if abs(target) > total_sum:
            return 0  # 此时没有方案
        if (target + total_sum) % 2 == 1:
            return 0  # 此时没有方案
        target_sum = (target + total_sum) // 2  # 目标和
        dp = [0] * (target_sum + 1)  # 创建动态规划数组，初始化为0
        dp[0] = 1  # 当目标和为0时，只有一种方案，即什么都不选
        for num in nums:
            for j in range(target_sum, num - 1, -1):
                dp[j] += dp[j - num]  # 状态转移方程，累加不同选择方式的数量
        return dp[target_sum]  # 返回达到目标和的方案数

一和零

思路：这个背包有两个维度，一个是m 一个是n，而不同长度的字符串就是不同大小的待装物品。
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。 dp[i][j]
就可以是 dp[i - zeroNum][j - oneNum] + 1。 然后在遍历的过程中，取dp[i][j]的最大值。

def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
    dp = [[0] * (n + 1) for _ in range(m + 1)]  # 创建二维动态规划数组，初始化为0
    for s in strs:  # 遍历物品
        zeroNum = s.count('0')  # 统计0的个数
        oneNum = len(s) - zeroNum  # 统计1的个数
        for i in range(m, zeroNum - 1, -1):  # 遍历背包容量且从后向前遍历
            for j in range(n, oneNum - 1, -1):
                dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)  # 状态转移方程
    return dp[m][n]