1
class Solution:
2
    def lastStoneWeightII(self, stones: List[int]) -> int:
3
        sum_weight = sum(stones)
4
        # dp[i][j] 表示前 i 个石头能否组成重量 j 的最大重量
5
        dp = [[0] * (sum_weight // 2 + 1) for _ in range(len(stones) + 1)]
6

7
        for i in range(1, len(stones) + 1):
8
            cur = stones[i - 1]
9
            for j in range(sum_weight // 2 + 1):
10
                if j >= cur:
11
                    # 可以选当前石头
12
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cur] + cur)
13
                else:
14
                    # 不能选当前石头
15
                    dp[i][j] = dp[i - 1][j]
16

17
        # 最大可达的重量 max_weight，差值即为 total - 2 * max_weight
18
        max_weight = dp[len(stones)][sum_weight // 2]
19
        return sum_weight - max_weight * 2

1
class Solution:
2
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
3
        self.memo = {}
4
        if len(nums) == 0:
5
            return 0
6
        return self.dp(nums, 0, target)
7

8
    def dp(self, nums, i, remain):
9
        # 终止条件：遍历完整个数组
10
        if i == len(nums):
11
            return 1 if remain == 0 else 0
12

13
        key = f"{i},{remain}"
14
        if key in self.memo:
15
            return self.memo[key]
16

17
        # 选择：加 nums[i] 或 减 nums[i]
18
        result = self.dp(nums, i + 1, remain - nums[i]) + \
19
                 self.dp(nums, i + 1, remain + nums[i])
20

21
        self.memo[key] = result
22
        return result

1
class Solution:
2
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
3
        # 初始化三维数组：dp[i][j][k]
4
        dp = [[[0] * (n + 1) for _ in range(m + 1)] for _ in range(len(strs) + 1)]
5

6
        for i in range(1, len(strs) + 1):
7
            curStr = strs[i - 1]
8
            zeroCount = curStr.count('0')
9
            oneCount = curStr.count('1')
10

11
            for j in range(m + 1):
12
                for k in range(n + 1):
13
                    if j >= zeroCount and k >= oneCount:
14
                        # 两种情况：选 or 不选
15
                        dp[i][j][k] = max(
16
                            dp[i - 1][j - zeroCount][k - oneCount] + 1,
17
                            dp[i - 1][j][k]
18
                        )
19
                    else:
20
                        # 容量不足，不能选
21
                        dp[i][j][k] = dp[i - 1][j][k]
22

23
        return dp[len(strs)][m][n]