# 方式一：自顶向下（带备忘录的递归）→ 更适合思考memo = {}def dp(state): if state in memo: return memo[state] if base_case: return base_val # 做选择 res = min/max(选择1, 选择2, ...) memo[state] = res return res# 方式二：自底向上（迭代）→ 更高效dp = [base_val] * (n + 1)for i in range(1, n + 1): for choice in choices: dp[i] = min/max(dp[i], dp[i - choice] + cost)return dp[n]
三、DP 常见模型
模型 1：线性 DP（一维）
# 爬楼梯 —— 最基础的 DPdef climb_stairs(n): if n <= 2: return n dp = [0] * (n + 1) dp[1], dp[2] = 1, 2 for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n]# 空间优化def climb_stairs_optimized(n): if n <= 2: return n a, b = 1, 2 for _ in range(3, n + 1): a, b = b, a + b return b
模型 2：打家劫舍（选或不选）
# dp[i] = max(dp[i-1], dp[i-2] + nums[i])def rob(nums): if not nums: return 0 if len(nums) == 1: return nums[0] dp = [0] * len(nums) dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i in range(2, len(nums)): dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) return dp[-1]# 空间优化版def rob_optimized(nums): prev2, prev1 = 0, 0 for num in nums: prev2, prev1 = prev1, max(prev1, prev2 + num) return prev1
模型 3：背包 DP
# 0-1 背包：dp[j] = max(dp[j], dp[j - w] + v) 倒序遍历！def knapsack_01(weights, values, capacity): dp = [0] * (capacity + 1) for w, v in zip(weights, values): for j in range(capacity, w - 1, -1): # 倒序！ dp[j] = max(dp[j], dp[j - w] + v) return dp[capacity]# 完全背包：dp[j] = max(dp[j], dp[j - w] + v) 正序遍历！def knapsack_complete(weights, values, capacity): dp = [0] * (capacity + 1) for w, v in zip(weights, values): for j in range(w, capacity + 1): # 正序！ dp[j] = max(dp[j], dp[j - w] + v) return dp[capacity]
零钱兑换（完全背包）：
def coin_change(coins, amount): dp = [amount + 1] * (amount + 1) dp[0] = 0 for coin in coins: for j in range(coin, amount + 1): dp[j] = min(dp[j], dp[j - coin] + 1) return dp[amount] if dp[amount] != amount + 1 else -1
模型 4：子序列 DP
# 最长递增子序列 LIS —— O(n^2)def length_of_lis(nums): if not nums: return 0 dp = [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)# 进阶：贪心 + 二分 O(n log n)def length_of_lis_optimized(nums): tails = [] for num in nums: idx = bisect_left(tails, num) if idx == len(tails): tails.append(num) else: tails[idx] = num return len(tails)
# 最长公共子序列 LCS —— 二维 DPdef longest_common_subsequence(text1, text2): m, n = len(text1), len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if text1[i - 1] == text2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n]
模型 5：编辑距离
def edit_distance(word1, word2): m, n = len(word1), len(word2) dp = [[0] * (n + 1) for _ in range(m + 1)] # 初始化边界 for i in range(m + 1): dp[i][0] = i # 删除 i 次 for j in range(n + 1): dp[0][j] = j # 插入 j 次 for i in range(1, m + 1): for j in range(1, n + 1): if word1[i - 1] == word2[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = 1 + min( dp[i - 1][j], # 删除 word1[i] dp[i][j - 1], # 插入 word2[j] dp[i - 1][j - 1] # 替换 ) return dp[m][n]
模型 6：路径 DP
# 不同路径def unique_paths(m, n): dp = [[1] * n for _ in range(m)] for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i - 1][j] + dp[i][j - 1] return dp[m - 1][n - 1]# 最小路径和def min_path_sum(grid): m, n = len(grid), len(grid[0]) dp = [[0] * n for _ in range(m)] dp[0][0] = grid[0][0] # 初始化边界 for i in range(1, m): dp[i][0] = dp[i - 1][0] + grid[i][0] for j in range(1, n): dp[0][j] = dp[0][j - 1] + grid[0][j] for i in range(1, m): for j in range(1, n): dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]) return dp[m - 1][n - 1]