当前位置：首页 > article >正文

＜代码随想录＞算法训练营-2024.12.19

article 2025/2/28 19:58:11

今日专题：动态规划完全背包（每个物品可以选n次）

动态规划分析的时候把状态转移图画出来

先遍历物品再遍历背包求排列数，先遍历背包再遍历物品求组合数

518. 零钱兑换 II

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:

        @cache
        def dfs(i, j):
            if j <= 0:
                return 1
            if i < 0:
                return 0

            if coins[i] > j:
                return dfs(i - 1, j)
            return dfs(i - 1, j) + dfs(i, j - coins[i])

        return dfs(len(coins) - 1, amount)

377. 组合总和 Ⅳ

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # 怎么处理不同排序是不同的结果呢
        # dp[i][j]=dp[i-1][j]+dp[i][j-nums[i]]
        size = len(nums)
        dp = [[0 for _ in range(target + 1)] for _ in range(size)]
        for i in range(size):
            dp[i][0] = 1

        for n in range(1, target + 1):
            for m in range(size):
                if n >= nums[m]:
                    dp[m][n] = dp[m - 1][n] + dp[-1][n - nums[m]]
                else:
                    dp[m][n] = dp[m - 1][n]

        return dp[size - 1][target]