Python动态规划案例有哪些？

wen python案例 2026-06-08 05:08:10 1

Python动态规划案例有哪些？从入门到进阶的10个经典实战解析

目录导读

动态规划核心思想与适用场景
经典入门案例
- 斐波那契数列（记忆化递归）
- 爬楼梯问题（状态转移方程）
二维动态规划案例
- 背包问题（0-1背包、完全背包）
- 最长公共子序列（LCS）
路径规划案例
- 不同路径与最小路径和
- 最大子数组和（Kadane算法）
字符串与区间DP案例
- 最长回文子串
- 编辑距离（Levenshtein距离）
常见面试与竞赛题型
- 股票买卖系列
- 打家劫舍问题
实战问答与调优技巧
如何高效掌握动态规划

动态规划核心思想与适用场景

动态规划（Dynamic Programming, DP）的核心是将复杂问题分解为重叠子问题，通过记忆化或自底向上填表避免重复计算，它适用于具有最优子结构和重叠子问题特性的题目。

关键问题与回答：

问：什么情况下优先考虑动态规划？
答：当你需要求最值（最大、最小）、计数（有多少种方式）、存在性（是否可达），且问题能通过决策链表逐步推导时，DP通常是首选，从左上角到右下角有多少种走法”就是典型计数DP。

经典入门案例

斐波那契数列（记忆化递归）

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

优化：使用自底向上迭代可将空间降为O(1)。

爬楼梯问题

问题：每次爬1或2阶，求到顶层的方法数。
状态定义：dp[i]表示到达第i阶的方法数。
转移方程：dp[i] = dp[i-1] + dp[i-2]。

def climbStairs(n):
    if n <= 2: return n
    a, b = 1, 2
    for _ in range(3, n+1):
        a, b = b, a + b
    return b

二维动态规划案例

0-1背包问题

问题：给定物品重量w和价值v，背包容量C，求最大价值。
状态：dp[i][j]表示前i个物品，容量j时的最大价值。
转移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。
一维优化：倒序遍历容量，dp[j] = max(dp[j], dp[j-w] + v)。

问：为什么0-1背包一维优化需要倒序？
答：倒序确保每个物品只被取一次，正序会变成完全背包。

最长公共子序列（LCS）

问题：两个字符串的最长公共子序列长度。
dp[i][j]表示text1[:i]和text2[:j]的LCS长度。
转移：

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])

路径规划案例

不同路径（LeetCode 62）

网格m x n，从左上到右下，只能向下或右，求路径数。
dp[i][j] = dp[i-1][j] + dp[i][j-1]，边界为第一行和第一列均为1。
变形：最小路径和（LeetCode 64），加法改为取最小值。

最大子数组和（Kadane算法）

问题：求连续子数组最大和。
状态：dp[i]表示以nums[i]结尾的最大子数组和。
转移：dp[i] = max(nums[i], dp[i-1] + nums[i])，最终答案取max(dp)。
空间压缩：直接用两个变量维护。

字符串与区间DP案例

最长回文子串（LeetCode 5）

区间DP：dp[i][j]表示s[i:j+1]是否为回文。
转移：dp[i][j] = (s[i]==s[j]) and (j-i<2 or dp[i+1][j-1])。
复杂度：O(n^2)时间，O(n^2)空间，可优化为O(n)中心扩展法。

编辑距离（LeetCode 72）

将word1转为word2的最少操作数（增、删、改）。
dp[i][j]表示word1[:i]到word2[:j]的距离。
初始化：dp[0][j]=j，dp[i][0]=i。
转移：若当前字符相同则dp[i][j]=dp[i-1][j-1]，否则取三种操作最小值+1。

常见面试与竞赛题型

股票买卖系列（LeetCode 121-188）

一次交易：记录历史最低价，求最大差价。
无限次交易：只要今天比昨天高，就累加利润。
冷冻期：设置三维状态dp[i][持有/不持有/冷冻]。
最多K次交易：二维DP，dp[k][i]表示第k次交易在第i天的最大收益。

打家劫舍（LeetCode 198-337）

直线排列：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。
环形排列：分两次DP，分别排除首和尾。
树形结构：后序遍历，每个节点返回[选该节点的最大值, 不选的最大值]。

实战问答与调优技巧

问：动态规划面试题总是想不到状态定义怎么办？
答：三步法——①确定问题结果是什么（通常作为dp的值）；②考虑影响结果的变量有哪些（作为dp的维度）；③尝试写出递推关系，如果不行，尝试增加维度或改变状态含义，常见状态定义技巧：dp[i]表示以i结尾的某种性质，或dp[i][j]表示区间[i,j]的最优解。

问：遇到大数取模问题如何处理？
答：在转移中添加% MOD，Python需注意负值取模，可使用(a + MOD) % MOD，例如组合数DP、路径计数等题目常需取10^9+7。

内存优化技巧：