动态规划

2026-02-11

1. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

class Solution:
    def rob(self, nums: List[int]) -> int:
        def dfs(i):
            if i >= n :
                return 0
            res = max( dfs(i+1), dfs(i+2) + nums[i])
            return res

        def dfs3(i):
            if i>=n :
                return 0
            if cache[i] != -1:
                return cache[i]
            res = max( dfs3(i+1), dfs3(i+2) + nums[i])
            cache[i] = res
            return res
        def dp1():
            f = [0] * (n+2)
            for i,x in enumerate(nums):
                f[i+2] = max(f[i+1], f[i] + x)
            return f[n+1]
        def dp2():
            f0,f1 = 0,0
            for i,x in enumerate(nums):
                new_f = max(f1, f0 + x)
                f0 = f1
                f1 = new_f
            return f1
        n = len(nums)
        cache = [-1] * n        
        return dp2()

2. 01背包

class Solution:
    def zero_one_knapsack(capacity: int, w: List[int], v: List[int]) -> int:
        n = len(w)
        def dfs(i,c):
            if i< 0:
                return 0
            if c < w[i]:
                return dfs(i-1, c)
            return max(dfs(i-1,c), dfs(i-1, c-w[i])+ v[i])
        def dp1():
            row = len(v)            
            dp_map = [[0] *(capacity+1) for _ in range(row + 1)]

            for i in range(row):
                for c in range(capacity+1):
                    if c >= w[i]:
                        dp_map[i+1][c] = max(dp_map[i][c], dp_map[i][c-w[i]] + v[i])
                    else:
                        dp_map[i+1][c] = dp_map[i][c]
            return dp_map[row][capacity]
        def dp2():
            row  = len(v)
            dp_map = [ 0 ] * (capacity + 1)
            for i in range(row):
                for c in range(capacity, w[i] - 1, -1):
                    dp_map[c] = max(dp_map[c], dp_map[c - w[i]] + v[i])
            return dp_map[capacity]

        return dfs(n-1, capacity)

3. 目标和

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        @cache
        def dfs(i, t):
            if i< 0 :
                return 1 if t == 0 else 0
            if t < nums[i]:
                return dfs(i-1, t)
            return dfs(i-1, t) + dfs(i-1, t - nums[i])

        def dp1():
            dp_map = [[0] * (target+1) for _ in range(n+1) ]
            dp_map[0][0] = 1
            for i in range(n):
                for t in range(target+1):
                    if nums[i] > t:
                        dp_map[i+1][t] = dp_map[i][t]
                    else:
                        dp_map[i+1][t] = dp_map[i][t] + dp_map[i][t-nums[i]]
            return dp_map[n][target]
        def dp2():
            dp_map = [0] * (target+1)
            dp_map[0] = 1
            for i in range(n):
                for t in range(target, nums[i]-1, -1):
                    dp_map[t] = dp_map[t] + dp_map[t - nums[i]]
            return dp_map[target]
        target += sum(nums)
        n = len(nums)
        if target %2 != 0 or target<0:
            return 0
        target //= 2
        return dp2()

4. 完全背包

class Solution:
    def unbounded_knapsack(capacity: int, w: List[int], v:List[int]) -> int:
        def dfs(i, c):
            if i < 0:
                return 0
            if w[i] > c:
                return dfs(i-1, c)
            return dfs(i-1,c) + dfs(i, c-w[i] + v[i])
        n = len(w)
        dfs(n-1, capacity)

5. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        @cache
        def dfs(i, c):
            if i< 0:
                return 0 if c==0 else inf
            if coins[i] > c:
                return dfs(i-1 , c)
            return min(dfs(i-1, c) , dfs(i, c - coins[i]) + 1)
        def dp1():
            dp_map = [[inf] * (amount + 1) for _ in range( n+ 1 )]
            dp_map[0][0] = 0
            for i in range(n):
                for t in range(amount+1):
                    if coins[i] > t:
                        dp_map[i+1][t] = dp_map[i][t]
                    else:
                        dp_map[i+1][t] = min(dp_map[i][t] , dp_map[i+1][t - coins[i]] + 1)
            return dp_map[n][amount] 
        def dp2():
            dp_map = [inf] * (amount+1)
            dp_map[0] = 0
            for i in range( n):
                for t in range(  coins[i], amount+1):
                    dp_map[t] = min(dp_map[t], dp_map[t-coins[i]] + 1 )
            return dp_map[amount]
        n = len(coins)
        res = dp2()
        return res if res < inf else -1