《动态规划教学》课件

动态规划教学一种解决复杂问题的强大算法思想，通过分解问题为子问题并存储结果提高计算效率课程导入应用场景路径规划资源分配背包问题序列分析生物信息学图像处理计算机视觉动态规划简介基本概念主要思想将复杂问题分解为简单子存储并复用子问题解问题历史发展贝尔曼1950年代提出动态规划的核心思想问题分解与子问题重叠最优子结构的利用将原始问题拆分成相互依赖的子问题问题最优解包含子问题最优解相同子问题多次出现由子问题的最优解构建出原问题解避免重复计算递推关系清晰明确基本步骤概览状态定义确定问题的状态表示方式状态转移方程建立子问题间的数学关系边界与初始条件设置初始值和特殊情况答案的获取从状态数组中提取最终结果与分治及递归的关系动态规划vs递归•存储中间结果•自底向上计算•避免重复计算动态规划vs分治•子问题有重叠•记忆化存储•效率更高适用动态规划的问题特征无后效性未来状态只与当前状态有关最优子结构原问题最优解包含子问题最优解子问题重叠性相同子问题被重复使用一维线性问题赏析DP序列型计数型处理线性序列相关问题统计满足条件的方案数最值型存在型求解最大或最小值问题判断是否存在解斐波那契数列问题状态dp[i]含义转移方程推导第i个斐波那契数的值dp

[0]=0最简单的动态规划范例dp

[1]=1dp[i]=dp[i-1]+dp[i-2]实例讲解斐波那契实现1递归写法时间复杂度O2^n带备忘录的递归时间复杂度On动态规划迭代时间复杂度On，空间On打家劫舍（）House Robber问题描述状态设计沿街房屋，不能抢劫相邻房屋dp[i]表示抢劫前i个房屋的最大收益求能抢到的最大金额考虑当前房屋抢或不抢两种情况状态转移公式及代码实现动态方程Python实现dp[i]=maxdp[i-1],dp[i-2]+nums[i-1]def robnums:if notnums:return0if lennums==1:return nums

[0]抢当前屋dp[i-2]+nums[i-1]不抢当前屋dp[i-1]dp=

[0]*lennums+1dp

[1]=nums

[0]for i in range2,lennums+1:dp[i]=maxdp[i-1],dp[i-2]+nums[i-1]return dp[lennums]打家劫舍进阶环形房屋环形排列特点问题分解最终结果首尾房屋不能同时抢分别考虑不抢第一间两种情况的最大值劫和不抢最后一间最大子序和（连续子数组最大和）问题描述寻找和最大的连续子数组状态定义dp[i]表示以第i个元素结尾的最大子序和转移方程dp[i]=maxnums[i],dp[i-1]+nums[i]实例讲解代码与优化2基本实现空间优化def maxSubArraynums:def maxSubArraynums:dp=

[0]*lennums curr_max=global_max=nums

[0]dp

[0]=nums

[0]for iin range1,lennums:for iin range1,lennums:curr_max=maxnums[i],curr_max+dp[i]=maxnums[i],dp[i-1]+nums[i]nums[i]global_max=maxglobal_max,curr_maxreturn maxdpreturnglobal_max零钱兑换（）Coin Change问题建模状态设计给定不同面额硬币，求凑成dp[i]表示凑成金额i所需的最目标金额所需最少硬币数少硬币数可重复使用每种硬币涉及完全背包问题思想转移方程dp[i]=mindp[i],dp[i-coin]+1零钱兑换典型解法自顶向下（记忆化递归）自底向上（动态规划）def coinChangecoins,amount,memo={}:def coinChangecoins,amount:if amountin memo:return memo[amount]dp=[floatinf]*amount+1if amount==0:return0dp

[0]=0if amount0:return-1for coinin coins:res=floatinf for iin rangecoin,amount+1:for coinin coins:dp[i]=mindp[i],dp[i-coin]+1sub=coinChangecoins,amount-coin,memoif sub!=-1:return dp[amount]if dp[amount]!=floatinfres=minres,sub+1else-1memo[amount]=-1if res==floatinf elseresreturnmemo[amount]二维入门DP状态表示转移方向使用二维数组记录状态通常从左、上或左上方转移常见应用边界初始化矩阵路径、字符串匹配、区间问题设置矩阵第一行和第一列初值最长公共子序列（）基础LCS问题描述找出两个字符串中最长的公共子序列子序列不要求连续状态设计dp[i][j]表示text1前i个字符与text2前j个字符的LCS长度二维表格记录匹配结果状态转移推导LCS字符相等dp[i][j]=dp[i-1][j-1]+1字符不等dp[i][j]=maxdp[i-1][j],dp[i][j-1]初始化dp

[0][j]=dp[i]

[0]=0LCS代码实现与空间优化标准实现空间优化def longestCommonSubsequencetext1,text2:def longestCommonSubsequencetext1,text2:m,n=lentext1,lentext2m,n=lentext1,lentext2dp=[

[0]*n+1for_in rangem+1]#保留两行for iin range1,m+1:dp=[

[0]*n+1for_in range2]for jin range1,n+1:if text1[i-1]==text2[j-1]:for iin range1,m+1:dp[i][j]=dp[i-1][j-1]+1curr,prev=i%2,i-1%2else:for jin range1,n+1:dp[i][j]=maxdp[i-1][j],dp[i][j-1]if text1[i-1]==text2[j-1]:dp[curr][j]=dp[prev][j-1]+1return dp[m][n]else:dp[curr][j]=maxdp[prev][j],dp[curr][j-1]return dp[m%2][n]编辑距离（）Edit Distance问题背景计算两个字符串的最小编辑距离操作定义插入、删除、替换字符状态定义dp[i][j]表示word1前i个字符转换到word2前j个字符的最小操作数状态转移考虑字符相等和不等两种情况编辑距离代码详解def minDistanceword1,word2:m,n=lenword1,lenword2dp=[

[0]*n+1for_in rangem+1]#边界初始化for iin rangem+1:dp[i]

[0]=ifor jin rangen+1:dp

[0][j]=j#填充dp表格for iin range1,m+1:for jin range1,n+1:if word1[i-1]==word2[j-1]:dp[i][j]=dp[i-1][j-1]else:dp[i][j]=mindp[i-1][j]+1,#删除dp[i][j-1]+1,#插入dp[i-1][j-1]+1#替换return dp[m][n]最小路径和（路径型）DP问题介绍状态表达方式在网格中找到从左上到右下dp[i][j]表示到达位置i,j的的最小路径和最小路径和每次只能向右或向下移动考虑从上方或左方到达转移方程dp[i][j]=grid[i][j]+mindp[i-1][j],dp[i][j-1]路径型状态转移DP二维实现使用m×n矩阵存储所有状态一维降维优化只保留一行状态，滚动更新空间复杂度从Om×n降至On背包问题系列0-1背包完全背包应用场景每个物品最多选择一次每个物品可以重复选择资源分配问题状态转移基于选择或不选择当前物品状态转移考虑多次选择同一物品物品组合优化子集和问题背包建模0-1状态定义选择考虑12dp[i][j]表示前i个物品在容量j下的最大价值不选第i个物品dp[i][j]=dp[i-1][j]3选择第i个物品4最终转移方程dp[i][j]=dp[i-1][j-w[i]]+v[i]dp[i][j]=maxdp[i-1][j],dp[i-1][j-w[i]]+v[i]完全背包与变种完全背包特点常见变种物品可无限次选择•多重背包每种物品有限定数量•混合背包包含多种类型物品状态转移不同于0-1背包•二维费用背包考虑重量和体积#0-1背包（物品只能用一次）•分组背包物品分组，每组最多选一个for iin range1,n+1:for jin rangeW,w[i]-1,-1:dp[j]=maxdp[j],dp[j-w[i]]+v[i]#完全背包（物品可重复使用）for iin range1,n+1:for jin rangew[i],W+1:dp[j]=maxdp[j],dp[j-w[i]]+v[i]背包问题实操确定状态与转移明确物品属性和背包容量初始化边界条件dp

[0][j]和dp[i]

[0]根据问题设置循环顺序设计0-1背包物品外循环，容量内循环逆序滚动数组优化使用一维数组降低空间复杂度区间典型问题DP截断型寻找最优切分点合并型子区间合并代价石子合并问题相邻石子堆合并，求最小总成本区间状态设计DP子问题定义dp[i][j]表示区间[i,j]上的最优解计算顺序按区间长度从小到大计算拆分策略枚举区间内的分割点区间转移方程DP区间分割状态合并区间遍历顺序枚举分割点k，其中i≤k dp[i][j]=min/maxdp[i][k]+需要保证计算dp[i][j]时，所有更dp[k+1][j]+costi,j小的区间已计算完毕将区间[i,j]分为[i,k]和[k+1,j]不同问题有不同的合并成本cost区间DP代码实战石子合并实现常见实现误区•循环顺序错误，必须从小区间到大区间def mergeStonesstones:•边界条件处理不当n=lenstones•分割点k范围设置错误#前缀和，快速计算区间和•合并成本计算错误prefix=

[0]*n+1for iin rangen:prefix[i+1]=prefix[i]+stones[i]#dp[i][j]表示合并区间[i,j]的最小成本dp=[[floatinf]*n for_in rangen]#初始化单个石子的成本为0for iin rangen:dp[i][i]=0#按区间长度计算for lengthin range2,n+1:for iin rangen-length+1:j=i+length-1for kin rangei,j:dp[i][j]=mindp[i][j],dp[i][k]+dp[k+1][j]+prefix[j+1]-prefix[i]return dp

[0][n-1]记忆化搜索（递归备忘录）+核心思想自顶向下计算，存储已解决子问题结果适用场景状态转移复杂，递归更直观实现方式递归函数+哈希表/数组存储中间结果特点优势按需计算，避免不必要的状态计算状态压缩动态规划核心思想适用场景用二进制位表示状态集合状态数量有限，可用二进制表示减少状态表示空间如旅行商TSP问题典型操作检查位state1i设置位state|1i清除位state~1i状态压缩DP详解与技巧TSP问题建模解决状态空间爆炸的技巧•利用问题对称性减少状态#dp[mask][i]表示当前在城市i，已访问城市集合为mask•预处理状态关系，避免重复计算#的最短路径长度•使用滚动数组优化空间def tspgraph:•剪枝排除不可能的状态n=lengraph•分解将大问题分解为子问题#1n表示所有城市的访问状态dp=[[floatinf]*n for_in range1n]#初始状态只访问城市0dp

[1]

[0]=0#枚举所有状态for maskin range1,1n:for iin rangen:#如果城市i在mask中if mask1i:#枚举前一个访问的城市jfor jin rangen:if j!=i andmask1j:dp[mask][i]=mindp[mask][i],dp[mask^1i][j]+graph[j][i]#所有城市都访问过，最后回到起点0return mindp[1n-1][i]+graph[i]

[0]for iin range1,n树形简要介绍DP基本概念典型例题状态定义常依赖于树的结构树的最大独立集问题一般在树上自底向上传递状树的最小顶点覆盖态树的直径计算状态设计通常dp[node][0/1]表示选择或不选择当前节点的最优解利用后序遍历自底向上计算单调队列优化DP核心思想优化目标常用应用维护单调递增或递减将On²优化到On滑动窗口最大/最小的队列值问题实现要点队列保持元素单调性，删除无用元素单调队列DP实例滑动窗口最大值问题单调队列实现给定数组和窗口大小k，求每个窗口内的最大值from collectionsimport deque朴素解法需要Onk时间复杂度def maxSlidingWindownums,k:单调队列可优化到Onif notnums ork==0:return[]result=[]q=deque#存储下标for iin rangelennums:#删除队列中不在当前窗口的元素while qand q

[0]i-k+1:q.popleft#删除队列中所有小于当前元素的值while qand nums[q[-1]]nums[i]:q.pop#将当前元素下标加入队列q.appendi#当窗口形成后，记录结果if i=k-1:result.appendnums[q

[0]]return result滚动数组空间优化核心思想应用条件典型优化复用存储空间，降低当前状态只依赖于有二维DP优化为一维数空间复杂度限的前几个状态组常见模式使用取模操作dp[i%2][j]替代dp[i][j]动态规划实现的常见陷阱状态表达遗漏未考虑所有可能的状态转移边界条件错误初始化不当或特殊情况未处理状态依赖顺序错误计算顺序与依赖关系不符整型溢出累加结果超出数据类型范围动态规划调试与排错指南打印DP数组查看中间状态计算是否符合预期手动跟踪小规模样例与程序计算结果对比验证检查边界条件测试特殊输入和极限情况逐步构建复杂度从简单情况开始，逐步增加复杂度竞赛面试中的动态规划/LeetCode热门题目70阶梯问题、53最大子序和、139单词拆分、322零钱兑换、416分割等和子集、1143最长公共子序列动态规划模板总结#一维动态规划模板def dp_1dproblem_input:#

1.状态定义n=lenproblem_inputdp=[initial_value]*n+1#

2.初始化dp

[0]=base_case#

3.状态转移for iin range1,n+1:dp[i]=transfer_functiondp[i-1],problem_input[i-1]#

4.返回结果return dp[n]#二维动态规划模板def dp_2dinput1,input2:#

1.状态定义m,n=leninput1,leninput2dp=[[initial_value]*n+1for_in rangem+1]#

2.初始化dp

[0]

[0]=base_case#

3.状态转移foriin range1,m+1:for jinrange1,n+1:dp[i][j]=transfer_functiondp[i-1][j],dp[i][j-1],dp[i-1][j-1],input1[i-1],input2[j-1]#

4.返回结果return dp[m][n]动态规划能力提升路径基础理论学习掌握核心概念和基本题型经典题目练习按难度递增刷题，强化理解解题模式识别总结解题模式，快速匹配题型高级技巧应用掌握状态压缩等优化方法动态规划进阶与应用拓展图算法融合机器学习中的应用•最短路径问题的DP解法•马尔可夫决策过程•图中的最长路径•时间序列预测•带约束的路径规划•强化学习中的Q-learning•序列对齐算法开源动态规划算法工具推荐工具VisuAlgo、Algorithm Visualizer、LeetCode、Codeforces、HackerRank等平台提供大量动态规划练习题和可视化工具常见面试笔试真题精讲/互联网公司高频题ACM竞赛经典题•最长回文子串•多重背包优化•戳气球问题•数位DP•正则表达式匹配•四边形不等式优化解题技巧•沟通问题边界•从暴力递归到DP的思路转换•复杂度分析与优化思路课堂答疑与学员互动如何判断问题是否适合DP正确设计状态的方法检查是否具有最优子结构和重叠子问题思考决策过程中需要记录哪些信息从递归到递推的转换技巧调试DP代码的常用方法分析递归调用依赖图，确定递推顺序小规模测试，打印中间状态总结与课后作业核心要点回顾课后练习状态定义、转移方程、边界条件背包问题变种、区间DP应用学习小组拓展阅读组队讨论复杂问题，互相讲解《算法导论》动态规划章节。