动态规划算法python

从〈状态定义〉到〈最优子结构〉,用Python构建高效思维。本指南覆盖网民最常搜索的背包问题、最长递增子序列、编辑距离等,并提供可直接运行的代码片段。

⚙️ 为什么选择Python?

  • 简洁语法快速验证状态转移方程
  • 丰富的内置结构(列表、字典)实现记忆化
  • 〈@lru_cache〉装饰器一行优化递归

※ 今日聚焦

【背包九讲】Python实现、区间DP模板、股票买卖系列。网友还关心:如何从暴力递归推导出动态规划。

⚡ 核心进阶 · 时间轴

① 递归 斐波那契数列 → 重叠子问题识别。Python中朴素递归导致指数爆炸。
② 记忆化 使用字典或functools.lru_cache存储中间结果,时间复杂度降至O(n)。
③ 递推 自底向上构建DP表,例如0/1背包的二维数组优化。
④ 空间优化 滚动数组技巧,将O(n*m)压缩至O(m),Python列表原地更新。

〈状态〉与〈选择〉是动态规划的核心。定义dp[i]的含义往往决定解题方向。

〔 经典专题 〕选项卡详解

0/1背包 · Python实现

状态定义:dp[i][w] 表示前i个物品容量w的最大价值。转移方程:dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]]+val[i])。

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0]*(capacity+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for w in range(1, capacity+1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]]+values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][capacity]

网友还关心:完全背包与多重背包的Python优化写法。

最长递增子序列 (LIS)

给定数组[10,9,2,5,3,7,101,18],输出4。使用dp[i]表示以i结尾的LIS长度。时间复杂度O(n²),二分优化至O(n log n)。

def lengthOfLIS(nums):
    dp = [1]*len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j]+1)
    return max(dp)

编辑距离 · 字符串转换

将word1转换成word2的最少操作数。〈插入〉〈删除〉〈替换〉各计一步。dp[i][j]表示前缀子串的最小编辑距离。

def minDistance(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
    for j in range(n+1): dp[0][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],dp[i][j-1],dp[i-1][j-1])
    return dp[m][n]

硬币找零 · 最少硬币数

coins=[1,2,5], amount=11,输出3(5+5+1)。完全背包变种,dp[i]表示金额i所需最少硬币。

def coinChange(coins, amount):
    dp = [float('inf')]*(amount+1)
    dp[0]=0
    for coin in coins:
        for x in range(coin, amount+1):
            dp[x] = min(dp[x], dp[x-coin]+1)
    return dp[amount] if dp[amount]!=float('inf') else -1

「网友们还关心」热点聚焦

◤ 状态转移方程推导技巧

明确〈base case〉、〈选择〉、〈状态〉。例如打家劫舍问题:dp[i] = max(dp[i-1], dp[i-2]+nums[i])。

◤ Python记忆化递归模板

from functools import lru_cache 然后使用@lru_cache(None)装饰函数,自动缓存结果。

◤ 区间DP · 戳气球

定义dp[i][j]为开区间(i,j)最大硬币数。Python实现时注意边界处理。

◤ 股票买卖最佳时机

多维状态:dp[i][k][0/1]表示第i天交易k次是否持有。网友常搜“冷冻期”变种。

【高频问答】动态规划算法python

常见疑问简明解答
如何判断一道题用DP?存在〈重叠子问题〉+〈最优子结构〉,求最值/计数/可行性。
Python递归深度限制?使用sys.setrecursionlimit()或改用迭代递推。
二维DP如何降维?观察状态只依赖上一行,用一维数组倒序/正序更新。
记忆化搜索与递推区别?记忆化自顶向下,递推自底向上,时间复杂度相同。

ⅰ 网友还搜索:“动态规划python背包问题详解”“DP状态压缩技巧”。

※ 周边深度 · 动态规划与Python生态

⑶ 矩阵链乘法

给定矩阵序列,求最少乘法次数。dp[i][j] = min(dp[i][k]+dp[k+1][j]+p[i-1]p[k]p[j])。Python实现常用三层循环。

⑷ 正则表达式匹配

LeetCode 10:实现 '.' 和 '*' 的支持。dp[i][j]表示s前i个与p前j个匹配,需仔细处理*号。

〈§ 学习路径〉:递归树 → 记忆化 → 递推 → 空间优化。配合Python的简洁特性,快速验证思路。