Python动态规划：从基础到高阶优化的全面指南(2)

四、动态规划优化技巧

4.1 状态压缩：空间复杂度优化

滚动数组技巧：

def knapsack_01_optimized(weights, values, capacity):n = len(weights)dp = [0] * (capacity+1)for i in range(n):# 逆序更新避免覆盖for w in range(capacity, weights[i]-1, -1):dp[w] = max(dp[w], dp[w-weights[i]] + values[i])return dp[capacity]

状态变量缩减：

def max_subarray(nums):"""最大子数组和 - Kadane算法"""current_max = global_max = nums[0]for i in range(1, len(nums)):current_max = max(nums[i], current_max + nums[i])global_max = max(global_max, current_max)return global_max

4.2 记忆化搜索：自顶向下实现

from functools import lru_cachedef longest_increasing_subsequence(nums):@lru_cache(maxsize=None)def dp(i):"""以nums[i]结尾的最长递增子序列长度"""max_len = 1for j in range(i):if nums[j] < nums[i]:max_len = max(max_len, dp(j) + 1)return max_lenreturn max(dp(i) for i in range(len(nums)))# 测试
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(longest_increasing_subsequence(nums))  # 输出：4 (2,5,7,101)

4.3 斜率优化：时间复杂度优化

def max_profit_k_transactions(prices, k):"""股票买卖K次最大利润"""n = len(prices)if n < 2: return 0# 如果k过大，退化为贪心if k >= n//2:return sum(max(0, prices[i]-prices[i-1]) for i in range(1, n))# dp[i][j] 第i天完成j次交易的最大利润dp = [[0]*(k+1) for _ in range(n)]for j in range(1, k+1):# 优化：记录前一天的最大值pre_max = -prices[0]for i in range(1, n):# 状态转移方程dp[i][j] = max(dp[i-1][j], prices[i] + pre_max)pre_max = max(pre_max, dp[i][j-1] - prices[i])return dp[n-1][k]# 测试
prices = [3, 2, 6, 5, 0, 3]
print(max_profit_k_transactions(prices, 2))  # 输出：7 (2->6, 0->3)

五、动态规划在工程中的应用

5.1 自然语言处理：分词优化

def word_break(s, word_dict):"""单词拆分问题：判断字符串是否可分割"""n = len(s)# dp[i]表示s[0:i]是否可拆分dp = [False] * (n+1)dp[0] = Truefor i in range(1, n+1):for j in range(i):if dp[j] and s[j:i] in word_dict:dp[i] = Truebreakreturn dp[n]# 测试
s = "applepenapple"
word_dict = {"apple", "pen"}
print(word_break(s, word_dict))  # True

5.2 图像处理：最短路径识别

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] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]return dp[m-1][n-1]# 测试
grid = [[1, 3, 1],[1, 5, 1],[4, 2, 1]
]
print(min_path_sum(grid))  # 输出：7 (1->3->1->1->1)

5.3 金融分析：期权定价

def option_pricing(S, K, T, r, sigma, N=1000):"""二叉树期权定价模型"""dt = T / N  # 时间步长u = np.exp(sigma * np.sqrt(dt))  # 上涨因子d = 1 / u  # 下跌因子p = (np.exp(r * dt) - d) / (u - d)  # 风险中性概率# 创建二叉树末节点价值values = np.zeros(N+1)for i in range(N+1):ST = S * (u ** i) * (d ** (N - i))values[i] = max(0, ST - K)  # 看涨期权# 反向递推计算当前价值for step in range(N-1, -1, -1):for i in range(step+1):values[i] = np.exp(-r * dt) * (p * values[i+1] + (1-p) * values[i])return values[0]# 测试
price = option_pricing(S=100, K=100, T=1, r=0.05, sigma=0.2)
print(f"期权理论价格: {price:.2f}")  # 约10.45

六、高阶动态规划技术

6.1 状态机动态规划

def max_profit_with_cool_down(prices):"""含冷冻期的股票买卖"""n = len(prices)if n < 2: return 0# 状态定义：# dp[i][0]: 持有股票# dp[i][1]: 不持有股票，处于冷冻期# dp[i][2]: 不持有股票，不处于冷冻期dp = [[0]*3 for _ in range(n)]# 初始化dp[0][0] = -prices[0]for i in range(1, n):# 状态转移dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i])dp[i][1] = dp[i-1][0] + prices[i]  # 卖出dp[i][2] = max(dp[i-1][1], dp[i-1][2])return max(dp[n-1][1], dp[n-1][2])# 测试
prices = [1, 2, 3, 0, 2]
print(max_profit_with_cool_down(prices))  # 输出：3 (1买,2卖,0买,2卖)

6.2 数位动态规划

def count_digit_one(n):"""计算1~n所有数字中1出现的次数"""s = str(n)@lru_cache(maxsize=None)def dp(pos, cnt, tight):"""递归函数pos: 当前处理位置cnt: 已计数1的个数tight: 是否受前导零限制"""if pos == len(s):return cntlimit = int(s[pos]) if tight else 9total = 0for digit in range(limit + 1):next_tight = tight and (digit == limit)next_cnt = cnt + 1 if digit == 1 else cnttotal += dp(pos+1, next_cnt, next_tight)return totalreturn dp(0, 0, True)# 测试
print(count_digit_one(13))  # 输出：6 (1,10,11,12,13)

6.3 树形动态规划

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef rob_tree(root):"""二叉树房屋抢劫问题"""def dp(node):"""返回(偷当前节点的最大值, 不偷当前节点的最大值)"""if not node:return 0, 0left = dp(node.left)right = dp(node.right)# 偷当前节点：当前值 + 不偷子节点rob_curr = node.val + left[1] + right[1]# 不偷当前节点：取子节点最大值not_rob = max(left) + max(right)return rob_curr, not_robreturn max(dp(root))# 测试
#     3
#    / \
#   2   3
#    \   \ 
#     3   1
root = TreeNode(3)
root.left = TreeNode(2, None, TreeNode(3))
root.right = TreeNode(3, None, TreeNode(1))
print(rob_tree(root))  # 输出：7 (3+3+1)