from functools import cache
from typing import List

"""01背包问题"""
"""求方案数问题 总方案数：两个互斥方案相加"""

def zero_one_knapsack(capacity: int, weights: list[int], values: list[int]):
    n = len(weights)
    @cache
    def dfs(i, c):
        if i < 0:
            return 0
        if c < weights[i]:
            return dfs(i-1, c)
        return max(dfs(i-1, c), dfs(i-1, c-weights[i]) + values[i])
# 变形 ：
"""
至多装 capacity 求方案数/最大价值和
恰好装 capacity 求方案数/最大/最小价值和
至少装 capacity 求方案数/最小价值和
"""
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # 和->s 整数和->p 负数和->s-p 目标-> p - (s - p)
        # 转换问题 在nums里寻找恰好和等于 p=(s+t)/2 的方案数
        target += sum(nums)

        if target < 0 or target % 2: # 偶数或者小于0方案数为0
            return 0
        target = target // 2
        n = len(nums)
        @cache
        def dfs(i, c):
            if i < 0:
                return 1 if c == 0 else 0
            if c < nums[i]:
                return dfs(i-1, c)
            # 选或者不选
            return dfs(i-1, c) + dfs(i-1, c-nums[i])
        return dfs(n - 1, target)

@cache实在是太好用了！

OωO