《Python编程动态规划》课件

编动态规划Python程欢迎来到《Python编程动态规划》课程本课程将深入探讨动态规划这一强大的算法设计技巧，并通过Python语言实现various经典问题的解决方案我们将从基础概念开始，逐步深入到复杂应用，帮助您掌握这一重要的编程技能课标程目动态规划问题骤理解原理掌握解决步深入理解动态规划的核心概念和思想，包括最优子结构、重叠学习如何识别动态规划问题，并系统地应用解决步骤子问题等练实现复杂熟Python分析算法度通过大量实践，掌握使用Python语言高效实现动态规划算法学会分析动态规划算法的时间和空间复杂度，优化解决方案的技巧动态规划概述义应领定用域动态规划是一种通过将复杂问题分解为更简单的子问题来解决问题动态规划在多个领域有广泛应用，包括算法设计、机器学习、自然的方法它通过存储子问题的解来避免重复计算，从而提高效率语言处理、生物信息学等它能够解决诸如最短路径、资源分配、序列对齐等问题动态规划的特点优结构叠问题态转最子重子状移问题的最优解包含子问在求解过程中，相同的通过定义问题状态和状题的最优解这意味着子问题会被多次计算态之间的转移关系，我我们可以通过解决子问动态规划通过存储这些们可以建立递推公式，题来构建整体问题的解结果来避免重复计算从而逐步求解问题动态规划问题骤解决步义态

1.定状明确定义问题的状态，通常是子问题的解态转

2.建立状移方程找出状态之间的关系，建立递推公式边

3.确定界条件明确初始状态和终止条件计顺

4.算序决定是自顶向下还是自底向上求解优间

5.化空考虑是否可以优化存储空间经动态规划问题典-斐波那契数列问题动态规划描述思路斐波那契数列是一个经典的动态规划问题数列定义为Fn=我们可以利用动态规划的思想，避免递归过程中的重复计算通过Fn-1+Fn-2，其中F0=0，F1=1存储已计算的结果，我们可以大大提高计算效率态义转状定和移方程态义状定定义dp[i]表示第i个斐波那契数转移方程dp[i]=dp[i-1]+dp[i-2]边界条件dp

[0]=0,dp

[1]=1标目求解dp[n]，即第n个斐波那契数动态规划实现自底向上def fib_bottom_upn:if n=1:return ndp=

[0]*n+1dp

[1]=1for iin range2,n+1:dp[i]=dp[i-1]+dp[i-2]return dp[n]这种方法从最小的子问题开始，逐步构建更大的问题解它避免了递归调用，效率更高，特别是对于大型输入顶动态规划实现自向下def fib_top_downn,memo={}:if nin memo:return memo[n]if n=1:return nmemo[n]=fib_top_downn-1,memo+fib_top_downn-2,memoreturn memo[n]这种方法使用递归，但通过记忆化（memoization）存储已计算的结果，避免重复计算它更接近问题的自然思考方式，但可能导致栈溢出时间间复杂和空度分析时间复杂间复杂度空度两种方法的时间复杂度都是On，因为每个斐波那契数只被计算自底向上方法的空间复杂度是On，因为使用了一个长度为n+1的一次数组自顶向下方法的空间复杂度也是On，但还有额外的递归调用栈空间经动态规划问题问题典-背包背包问题是一类经典的组合优化问题，广泛应用于资源分配、投资决策等领域它考察如何在限制条件下实现价值最大化我们将讨论两种主要类型0-1背包问题和完全背包问题0-1背包完全背包每种物品要么放入背包，要么不放入，每种物品可以放入任意多次（在背包不能部分放入或多次放入容量允许的情况下）问题义0-1背包定问题约描述束条件给定n个物品，每个物品有一个每个物品只能选择放或不放，不重量w[i]和一个价值v[i]现在能部分放入总重量不能超过背有一个容量为W的背包，如何选包容量W择物品放入背包，使得总价值最大？标目在满足重量限制的条件下，使得放入背包的物品总价值最大态义转状定和移方程态义转状定移方程定义dp[i][j]表示考虑前i个物品，背包容量为j时能获得的最大价值dp[i][j]=maxdp[i-1][j],dp[i-1][j-w[i]]+v[i]if j=w[i]dp[i][j]=dp[i-1][j]if jw[i]这个转移方程考虑了两种情况不放入第i个物品，或放入第i个物品我们选择能够得到更大价值的情况经问题实现典0-1背包Pythondef knapsack_01W,w,v,n:dp=[[0for xin rangeW+1]for xin rangen+1]for iin range1,n+1:for jin range1,W+1:if w[i-1]=j:dp[i][j]=maxv[i-1]+dp[i-1][j-w[i-1]],dp[i-1][j]else:dp[i][j]=dp[i-1][j]return dp[n][W]这个实现使用二维数组来存储中间结果外层循环遍历物品，内层循环遍历背包容量时间复杂度为OnW，空间复杂度也为OnW问题义完全背包定问题描述与0-1背包类似，但每种物品可以选择任意多次（在背包容量允许的情况下）约束条件总重量不能超过背包容量W，每种物品可以选择0次或多次标目在满足重量限制的条件下，使得放入背包的物品总价值最大应场用景完全背包问题更适合模拟可重复使用的资源分配问题，如硬币找零、材料切割等问题态义转完全背包状定和移方程态义转状定移方程定义dp[i][j]表示考虑前i种物品，背包容量为j时能获得的最大价值dp[i][j]=maxdp[i-1][j],dp[i][j-w[i]]+v[i]if j=w[i]dp[i][j]=dp[i-1][j]if jw[i]与0-1背包不同，这里dp[i][j-w[i]]使用了当前行的数据，因为我们可以重复选择同一物品问题实现完全背包Pythondef knapsack_completeW,w,v,n:dp=

[0]*W+1for iin rangen:for jin rangew[i],W+1:dp[j]=maxdp[j],dp[j-w[i]]+v[i]return dp[W]这个实现使用一维数组优化了空间复杂度我们只需要一个长度为W+1的数组就可以解决问题时间复杂度为OnW，空间复杂度为OW经动态规划问题长典-最公共子序列最长公共子序列（Longest CommonSubsequence，LCS）问题是一个经典的动态规划问题，广泛应用于生物信息学、文本比较等领域它寻找两个序列中最长的共同部分，这些部分在原序列中不一定连续较设计生物信息学文本比算法用于比较DNA序列的相似性用于检测文本抄袭或版本控制系统作为其他复杂问题的子问题长义最公共子序列定问题描述给定两个序列X和Y，找出它们的最长公共子序列的长度子序列不要求在原序列中连续出现示例对于序列ABCDGH和AEDFHR，最长公共子序列是ADH，长度为3关键特点子序列元素在原序列中的相对顺序保持不变，但可以不连续战挑需要考虑所有可能的子序列组合，暴力解法的时间复杂度是指数级的态义转状定和移方程态义转状定移方程定义dp[i][j]表示序列X的前i个字符和序列Y的前j个字符的最长公如果X[i]==Y[j]dp[i][j]=dp[i-1][j-1]+1否则dp[i][j]=共子序列的长度maxdp[i-1][j],dp[i][j-1]这个转移方程考虑了两种情况当前字符相同时，LCS长度加1；当前字符不同时，选择不包含当前字符的最大LCS长度长实现最公共子序列Pythondef longest_common_subsequenceX,Y:m,n=lenX,lenYdp=[

[0]*n+1for_in rangem+1]for iin range1,m+1:for jin range1,n+1:if X[i-1]==Y[j-1]:dp[i][j]=dp[i-1][j-1]+1else:dp[i][j]=maxdp[i-1][j],dp[i][j-1]return dp[m][n]这个实现使用二维数组dp来存储中间结果外层循环遍历X序列，内层循环遍历Y序列时间复杂度为Omn，空间复杂度也为Omn，其中m和n分别是两个序列的长度经动态规划问题编辑离典-距编辑距离（Edit Distance），也称为Levenshtein距离，是衡量两个字符串相似度的一种方法它定义为将一个字符串转换成另一个字符串所需的最少单字符编辑操作次数检查语处拼写DNA序列分析自然言理用于自动纠正拼写错误比较DNA序列的相似度文本相似度计算和机器翻译编辑离义距定问题描述给定两个字符串str1和str2，计算将str1转换为str2所需的最少操作次数许允的操作插入一个字符、删除一个字符、替换一个字符示例字符串horse和ros的编辑距离为3操作步骤horse-rorse替换h为r-rose删除r-ros删除e应用在信息检索、拼写纠正、语音识别等领域有广泛应用态义转状定和移方程态义转状定移方程定义dp[i][j]表示将str1的前i个字符转换为str2的前j个字符所需的如果str1[i-1]==str2[j-1]dp[i][j]=dp[i-1][j-1]否则dp[i][j]最少操作次数=mindp[i-1][j],dp[i][j-1],dp[i-1][j-1]+1这个转移方程考虑了四种情况字符相同时不需操作，否则选择插入、删除或替换中的最小操作次数加1编辑离实现距Pythondef edit_distancestr1,str2:m,n=lenstr1,lenstr2dp=[

[0]*n+1for_in rangem+1]for iin rangem+1:dp[i]

[0]=ifor jin rangen+1:dp

[0][j]=jfor iin range1,m+1:for jin range1,n+1:if str1[i-1]==str2[j-1]:dp[i][j]=dp[i-1][j-1]else:dp[i][j]=mindp[i-1][j],dp[i][j-1],dp[i-1][j-1]+1return dp[m][n]这个实现使用二维数组dp来存储中间结果首先初始化边界条件，然后填充dp数组时间复杂度和空间复杂度都是Omn，其中m和n分别是两个字符串的长度动态规划实际应在中的用领习络规划金融域机器学网用于投资组合优化、期在序列模型、强化学习用于路由算法、网络流权定价等金融模型等领域有广泛应用量优化等戏发游开用于AI决策、路径规划等游戏逻辑实现动态规划不仅是一种算法技巧，更是解决复杂问题的思维方式它在许多实际应用中发挥着重要作用，帮助我们高效地解决各种优化问题问题股票交易问题约描述束条件给定一个数组，其中第i个元素是第i天的股票价格设计一个算法

1.你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股来计算你所能获取的最大利润你可以完成尽可能多的交易（多次票）

2.每天只能进行一次交易（买入或卖出）

3.不能在同一买卖一支股票）天买入并卖出股票这个问题是动态规划在金融领域的一个典型应用，它模拟了真实股市中的多次交易情况动态规划股票交易解决def max_profitprices:if notprices:return0profit=0for iin range1,lenprices:if prices[i]prices[i-1]:profit+=prices[i]-prices[i-1]return profit这个解决方案利用了贪心算法的思想，但本质上是一种动态规划方法我们遍历价格数组，只要当天价格比前一天高，就进行买卖操作这样可以保证获得最大利润时间复杂度为On，空间复杂度为O1问题最小路径和问题描述给定一个包含非负整数的m xn网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小动规则移每次只能向下或者向右移动一步应场用景这个问题在路径规划、网络路由等领域有广泛应用战挑需要考虑所有可能的路径，但暴力解法的时间复杂度是指数级的动态规划最小路径和解决def min_path_sumgrid:if not grid ornotgrid

[0]:return0m,n=lengrid,lengrid

[0]dp=[

[0]*n for_in rangem]dp

[0]

[0]=grid

[0]

[0]for iin range1,m:dp[i]

[0]=dp[i-1]

[0]+grid[i]

[0]for jin range1,n:dp

[0][j]=dp

[0][j-1]+grid

[0][j]for iin range1,m:for jin range1,n:dp[i][j]=mindp[i-1][j],dp[i][j-1]+grid[i][j]return dp[m-1][n-1]这个解决方案使用二维动态规划dp[i][j]表示到达i,j位置的最小路径和我们首先初始化第一行和第一列，然后填充dp数组时间复杂度和空间复杂度都是Omn币问题硬找零问题描述示例给定不同面额的硬币和一个总金额编写一个函数来计算可以凑成输入:coins=[1,2,5],amount=11输出:3解释:11=5+5+1总金额所需的最少的硬币个数如果没有任何一种硬币组合能组成总金额，返回-1这是一个典型的完全背包问题，每种硬币可以使用多次它在实际生活中有广泛应用，如自动售货机找零、银行柜台现金处理等币动态规划硬找零解决def coin_changecoins,amount:dp=[floatinf]*amount+1dp

[0]=0for coinin coins:for xin rangecoin,amount+1:dp[x]=mindp[x],dp[x-coin]+1return dp[amount]if dp[amount]!=floatinf else-1这个解决方案使用一维动态规划dp[i]表示凑成金额i所需的最少硬币数我们遍历每种硬币，更新所有可能的金额时间复杂度为Oamount*lencoins，空间复杂度为Oamount总结思考与问题分解动态规划的核心在于将复杂问题分解为简单子问题，并存储子问题的解以避免重复计算态义状定准确定义问题状态是解决动态规划问题的关键好的状态定义能大大简化问题解决过程转移方程找出状态之间的关系，建立清晰的转移方程是动态规划的核心步骤边界条件正确处理边界条件对于算法的正确性至关重要QA感谢大家参与本次《Python编程动态规划》课程我们已经深入探讨了动态规划的核心概念、经典问题及其Python实现现在是提问时间，欢迎大家就课程内容或者动态规划的其他方面提出问题码实现实际应概念澄清代用有关动态规划基本概念的疑问关于Python代码实现的具体问题动态规划在实际项目中的应用疑问。