动态规划算法入门与实战案例

20XX/XX/XX动态规划算法入门与实战案例汇报人:XXXCONTENTS目录01

动态规划基础认知02

动态规划核心原理03

动态规划解题步骤04

一维动态规划经典模型CONTENTS目录05

二维动态规划经典模型06

动态规划编程实战07

include<vector>#include<algorithm>usingnamespacestd;intlengthOfLIS(vector<int>&nums){if(nums.empty())return0;vector<int>dp(nums.size(),1);intmaxLen=1;for(inti=1;i<nums.size();++i){for(intj=0;j<i;++j){if(nums[j]<nums[i])dp[i]=max(dp[i],dp[j]+1);}maxLen=max(maxLen,dp[i]);}returnmaxLen;}08

动态规划应用场景01动态规划基础认知动态规划的定义动态规划（DynamicProgramming，DP）是一种通过将复杂问题分解为重叠子问题，并存储子问题的解来避免重复计算，从而高效求解最优解的算法设计思想。核心思想：分治与记忆化核心在于"拆分子问题、保存中间结果、避免重复计算"，通过将原问题分解为相互重叠的子问题，用空间换取时间，显著提升计算效率。动态规划的核心价值动态规划能够高效解决具有重叠子问题和最优子结构性质的优化问题，广泛应用于路径规划、资源分配、序列匹配等领域，是算法设计中的核心思想之一。动态规划的定义与核心价值动态规划与其他算法的区别动态规划vs暴力递归

暴力递归直接分解问题，无缓存机制，当子问题存在重叠时，会导致大量重复计算，时间复杂度极高；动态规划通过存储子问题的解来避免重复计算，显著提升效率。动态规划vs记忆化搜索

记忆化搜索采用递归+缓存的自顶向下方式，适用于子问题重叠且递归思路清晰的场景；动态规划则是迭代+状态表的自底向上方式，更侧重于求解最优解。动态规划vs贪心算法

贪心算法通过每步选择局部最优来试图得到全局最优，不存储子问题解，适用于具有贪心选择性质的问题；动态规划依赖子问题的最优解来推导全局最优，强调状态的存储与转移。动态规划的三大核心特性

最优子结构原问题的最优解包含其子问题的最优解，即子问题的解可以组合出原问题的解。例如，最短路径问题中，从A到C的最短路径一定包含从A到B的最短路径。

重叠子问题求解原问题时会反复遇到相同的子问题，若采用暴力递归会导致重复计算。动态规划通过存储子问题的解（如使用数组或哈希表）来避免这一问题，显著提升效率。

无后效性子问题的解一旦确定，不受后续决策影响。当前状态只依赖过去的状态，与未来的决策无关，确保了状态的稳定性和计算的可递推性。生活中的动态规划思想举例

旅行路线规划：最优子结构的应用从出发地到目的地规划最低费用路线时，将全程分解为多个城市间的子问题，每个阶段选择费用最低的中转城市，最终组合成全局最优路线。

学习计划制定：重叠子问题的优化备考时先掌握基础知识点（子问题），再逐步攻克综合题型。已学会的公式和方法可直接复用，避免重复学习，提升效率。

零钱兑换：状态转移的实践用1元、5元、10元兑换20元时，最优方案依赖于兑换19元、15元、10元的子问题解，通过递推找到最少硬币数，体现无后效性。

项目管理：分阶段决策的智慧将项目拆分为需求分析、开发、测试等阶段，每个阶段的最优进度安排（如资源分配）基于前一阶段的成果，确保整体项目高效推进。02动态规划核心原理最优子结构详解01最优子结构的定义最优子结构是动态规划的核心特性之一，指原问题的最优解包含其子问题的最优解。即通过求解子问题的最优解，可组合得到原问题的最优解。02核心特征子问题独立性：子问题的解可独立计算；组合性：子问题最优解能组合成原问题最优解；传递性：全局最优依赖局部最优的传递。03案例解析：最短路径问题从A到C的最短路径，若经过B点，则A→B和B→C的路径必为各自的最短路径。此例中，全局最优解（A→C）由子问题最优解（A→B、B→C）构成。04与贪心算法的区别动态规划通过子问题最优解推导全局最优，需存储中间结果；贪心算法直接选择局部最优，不依赖子问题解的存储，适用于具有贪心选择性质的问题。重叠子问题与计算优化

01重叠子问题的定义与影响重叠子问题指在问题求解过程中，相同子问题被多次重复计算的现象。如斐波那契数列中，计算F(5)需F(4)和F(3)，而F(4)又需F(3)和F(2)，导致F(3)被重复计算，暴力递归时间复杂度达O(2ⁿ)。

02记忆化搜索：自顶向下优化通过哈希表或数组缓存已计算的子问题解，当再次遇到相同子问题时直接返回结果。例如青蛙跳台阶问题，使用备忘录存储已计算的f(n)，将时间复杂度从O(2ⁿ)降至O(n)，空间复杂度O(n)。

03动态规划表：自底向上优化利用迭代方式从最小子问题开始计算，将结果存储在DP表中。如斐波那契数列使用一维数组dp[i]存储第i项值，按顺序计算避免重复，时间复杂度O(n)，空间复杂度可优化至O(1)（滚动数组）。

04空间优化：滚动数组与状态压缩当状态转移仅依赖有限个先前状态时，可用变量代替数组。例如爬楼梯问题中，用a、b两个变量滚动存储dp[i-2]和dp[i-1]，将空间复杂度从O(n)降至O(1)，不影响时间效率。无后效性的核心定义某阶段状态一旦确定，不受后续决策影响。当前状态仅依赖过去状态，与未来无关，确保子问题解的独立性与稳定性。无后效性的判断标准若问题的决策仅由当前状态决定，不依赖达成该状态的路径或历史决策，则满足无后效性。例如：最短路径问题中，节点A到B的最短距离不会因后续路径选择而改变。无后效性的应用意义保障动态规划算法的正确性，允许按固定顺序（如自底向上）计算状态，避免状态间的交叉影响，简化问题求解逻辑。典型案例：最短路径问题在有向无环图中，从起点到节点D的最短路径长度确定后，无论后续选择D到终点的哪条路径，D点的最短路径值始终不变，体现无后效性。无后效性原则及应用动态规划的时间与空间复杂度时间复杂度分析动态规划时间复杂度由状态数量和每个状态的计算时间决定，通常为O(N*M)，其中N和M是状态维度的规模，例如0-1背包问题的时间复杂度为O(n*C)，n为物品数量，C为背包容量。空间复杂度分析基础动态规划的空间复杂度与状态数量一致，如二维DP表为O(N*M)。通过滚动数组等优化技巧，可将空间复杂度降低，例如斐波那契数列从O(n)优化为O(1)，0-1背包从O(n*C)优化为O(C)。复杂度优化策略常见优化手段包括：状态压缩（如用一维数组替代二维数组）、滚动变量（仅保留最近的若干状态）、稀疏表存储（针对稀疏状态空间）。这些方法在不改变时间复杂度的前提下，显著降低空间需求。03动态规划解题步骤步骤一：定义状态

状态的核心概念状态是动态规划中描述子问题解的变量，通常用dp数组（如dp[i]或dp[i][j]）表示，需明确其代表的具体含义，是构建动态规划模型的基础。

状态定义的关键原则状态需紧扣问题目标，能完整描述子问题的核心信息，且便于推导状态转移关系，定义的好坏直接决定动态规划能否实现。

一维状态示例以最大子数组和问题为例，定义dp[i]表示以第i个元素结尾的最大子数组和，清晰聚焦子问题的最优解。

二维状态示例在不同路径问题中，定义dp[i][j]表示从左上角到(i,j)的路径数，通过二维数组记录二维空间下的子问题解。步骤二：确定状态转移方程

状态转移方程的定义描述当前状态与之前状态依赖关系的数学表达式，形如dp[i]=f(dp[i-1],dp[i-2],...)，是动态规划的核心逻辑。

核心：建立状态关联通过分析问题中不同状态间的递推关系，将复杂问题分解为可通过子问题解推导的形式，例如斐波那契数列中dp[i]=dp[i-1]+dp[i-2]。

推导方法与示例以最大子数组和为例，状态转移方程为dp[i]=max(nums[i],dp[i-1]+nums[i])，表示以第i个元素结尾的最大子数组和要么从当前元素重新开始，要么延续前一个子数组。

注意事项需确保方程覆盖所有可能情况，避免遗漏边界条件；同时保证无后效性，即当前状态仅依赖已计算的历史状态。步骤三：初始化边界条件边界条件的定义与作用边界条件是动态规划中最小子问题的解，是状态转移的起点，直接影响整个DP表的计算正确性。常见边界条件设定场景如斐波那契数列中dp[0]=0、dp[1]=1；爬楼梯问题中dp[0]=1（0阶台阶有一种方式）、dp[1]=1（1阶台阶一种方式）。初始化原则与注意事项需根据问题实际意义设定合理初始值，避免越界或逻辑错误。例如0-1背包问题中，dp[0][j]=0（前0个物品价值为0），dp[i][0]=0（容量为0时价值为0）。遍历顺序的核心原则遍历顺序需确保计算当前状态时，其依赖的所有子问题已被计算。即先解决"前置子问题"，再推导"当前问题"，避免因依赖未计算状态导致结果错误。常见遍历方向与场景一维DP多采用"从左到右"（如斐波那契数列、最大子数组和）；二维DP可按"行优先"或"列优先"（如不同路径问题按从上到下、从左到右遍历）；特殊场景需"从右到左"（如0-1背包空间优化时避免状态覆盖）。错误遍历顺序案例在计算dp[i]=dp[i-1]+dp[i-2]时，若从右向左遍历，计算dp[5]时dp[4]和dp[3]尚未计算，导致结果错误。正确顺序应为从左向右，依次计算dp[2]、dp[3]直至dp[n]。遍历顺序与状态依赖关系根据状态转移方程判断依赖方向：若dp[i]依赖dp[i-1]，则需顺序遍历；若依赖dp[i+1]，则需逆序遍历；二维DP若依赖dp[i-1][j]和dp[i][j-1]，则需按行或列正序遍历。步骤四：确定遍历顺序步骤五：计算最终结果

结果定位：DP表的目标位置原问题的解通常对应DP表的特定位置，如一维DP的dp[n]（斐波那契数列）、二维DP的dp[m-1][n-1]（不同路径问题）或dp数组的最大值（最大子数组和）。

结果提取：从状态表中获取答案根据问题定义，从已填充的DP表中直接读取目标状态值。例如最长递增子序列问题需遍历dp数组取最大值，0-1背包问题直接取dp[n][capacity]。

案例演示：不同路径问题结果计算对于m×n网格的不同路径问题，状态定义为dp[i][j]表示到达(i,j)的路径数，最终结果为dp[m-1][n-1]，通过遍历填充DP表后直接获取。

注意事项：边界与状态定义一致性确保结果提取位置与状态定义匹配，避免因索引偏移（如0-based或1-based）导致错误。例如爬楼梯问题中，dp[n]对应n阶台阶的解需与初始化条件对齐。04一维动态规划经典模型斐波那契数列问题解析问题定义与递推关系斐波那契数列定义：F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)（n≥2）。核心特征是每项等于前两项之和，体现动态规划的重叠子问题特性。暴力递归解法及缺陷直接递归实现F(n)=F(n-1)+F(n-2)，时间复杂度O(2ⁿ)，存在大量重复计算（如F(5)需计算F(4)和F(3)，F(4)又需F(3)和F(2)），n=30时计算量已达百万级。动态规划优化方案自底向上迭代：用数组dp存储子问题解，dp[i]=dp[i-1]+dp[i-2]，时间复杂度O(n)，空间复杂度O(n)。进一步优化为滚动变量存储前两状态，空间复杂度降至O(1)。代码实现与优化对比基础版使用dp数组：初始化dp[0]=0，dp[1]=1，循环计算dp[2..n]；优化版用a=0,b=1迭代更新，每次计算c=a+b后滚动赋值a=b,b=c，最终返回b。爬楼梯问题详解

问题描述假设有n阶楼梯，每次可爬1或2个台阶，求有多少种不同方法爬到顶部。示例：n=2时输出2（1+1、2）；n=3时输出3（1+1+1、1+2、2+1）。

状态定义与转移方程状态定义：dp[i]表示爬到第i阶的方法数。转移方程：dp[i]=dp[i-1]+dp[i-2]（从i-1阶爬1步或i-2阶爬2步）。

边界条件与初始化边界条件：dp[0]=1（0阶有1种方式：不爬），dp[1]=1（1阶只有1种爬法）。

代码实现与优化基础实现：用数组存储dp[0..n]，时间O(n)，空间O(n)。优化版本：用变量滚动存储前两状态，空间优化至O(1)。问题定义给定整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。状态定义dp[i]表示以第i个元素结尾的最大子数组和，核心是聚焦于以当前元素为结尾的子数组。状态转移方程dp[i]=max(nums[i],dp[i-1]+nums[i])，即要么从当前元素重新开始，要么延续前一个子数组。边界条件dp[0]=nums[0]，第一个元素的最大子数组和就是其本身。遍历顺序与结果提取从1到n-1遍历数组，遍历过程中记录dp数组的最大值，该最大值即为最大子数组和。空间优化无需存储完整dp数组，用变量cur_sum记录当前状态，max_sum记录全局最大值，空间复杂度从O(n)降至O(1)。最大子数组和问题一维动态规划空间优化技巧

空间优化核心思想当状态转移仅依赖有限的前序状态时，可通过变量滚动替代完整DP数组，将空间复杂度从O(n)降至O(1)。

单变量替代法（斐波那契数列）原需dp[i]=dp[i-1]+dp[i-2]，用a=dp[i-2]、b=dp[i-1]迭代更新：c=a+b→a=b→b=c，仅需3个变量。

双变量滑动窗口（最大子数组和）通过current_max记录以当前元素结尾的子数组和，global_max跟踪全局最大值，仅需2个变量完成迭代。

滚动数组优化策略对于依赖前k个状态的问题，使用固定大小为k的数组循环覆盖旧值，如爬楼梯问题用大小2的数组交替存储dp[i-1]和dp[i-2]。05二维动态规划经典模型问题描述一个机器人从m×n网格的左上角出发，每次只能向下或向右移动，求到达右下角共有多少条不同路径。状态定义定义dp[i][j]表示从(0,0)到(i,j)的路径数。状态转移方程dp[i][j]=dp[i-1][j]+dp[i][j-1]，即到达当前位置的路径数等于从上方和左方到达的路径数之和。边界条件第一行：dp[0][j]=1（只能从左方来）；第一列：dp[i][0]=1（只能从上方来）。遍历顺序行优先遍历（从上到下，从左到右），确保计算当前状态时，其依赖的子问题已被计算。代码实现初始化(m×n)dp表，边界值设为1，通过两层循环计算dp[i][j]，最终结果为dp[m-1][n-1]。不同路径问题解析0-1背包问题详解

问题定义与核心特征0-1背包问题是指给定n个物品（每个物品有重量w[i]和价值v[i]）和容量为C的背包，每个物品仅能选择放入或不放入，目标是在不超过背包容量的前提下最大化物品总价值。其核心特征是物品的不可分割性（0-1选择）和最优子结构性质。

动态规划状态定义定义二维数组dp[i][j]表示前i个物品在背包容量为j时的最大价值。其中i的范围是0到n（物品数量），j的范围是0到C（背包容量），状态值直接对应子问题的最优解。

状态转移方程推导对于第i个物品，若重量w[i-1]>j（当前容量不足），则dp[i][j]=dp[i-1][j]（不放入）；否则dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])（取放入与不放入的最大值）。

边界条件与初始化初始状态为dp[0][j]=0（0个物品时价值为0）和dp[i][0]=0（容量为0时价值为0）。通过双重循环填充dp表，外层遍历物品，内层遍历容量，时间复杂度为O(n*C)。

空间优化技巧使用一维数组dp[j]优化空间，容量维度从后向前遍历（避免覆盖未使用的子问题解），转移方程简化为dp[j]=max(dp[j],dp[j-w[i]]+v[i])，空间复杂度从O(n*C)降至O(C)。最长公共子序列问题问题定义与示例给定两个字符串，求它们最长公共子序列的长度。子序列是指字符按顺序出现但不一定连续。例如：输入"ABCBDAB"和"BDCAB"，输出4（对应子序列"BCAB"）。状态定义与转移方程状态定义：dp[i][j]表示字符串text1前i个字符与text2前j个字符的最长公共子序列长度。转移方程：若text1[i-1]==text2[j-1]，则dp[i][j]=dp[i-1][j-1]+1；否则dp[i][j]=max(dp[i-1][j],dp[i][j-1])。边界条件与计算顺序边界条件：当i=0或j=0时，dp[i][j]=0（空字符串与任何字符串的公共子序列长度为0）。计算顺序：按行优先或列优先遍历二维数组，确保子问题已求解。代码实现与复杂度使用二维数组存储dp表，时间复杂度O(mn)，空间复杂度O(mn)（m、n为两字符串长度）。优化后可使用一维数组将空间复杂度降至O(min(m,n))。二维动态规划空间优化技巧

二维转一维数组优化通过观察状态转移方程，若当前行只依赖上一行数据，可将二维DP表压缩为一维数组。例如0-1背包问题中，使用滚动数组保留前一行状态，空间复杂度从O(n*C)降至O(C)。

逆序遍历避免覆盖在一维数组优化时，采用逆序遍历容量维度（从大到小），确保计算当前状态时，所需的上一行左侧数据不被覆盖。如0-1背包中对容量j从C到w[i]逆序更新dp[j]。

状态压缩实例：不同路径原二维DP[i][j]=DP[i-1][j]+DP[i][j-1]，优化为一维数组后，dp[j]=dp[j]（上一行值）+dp[j-1]（当前行左侧值），仅需O(n)空间完成m×n网格路径计算。

通用优化原则优先识别状态转移的依赖方向（如仅依赖上一行/列），其次通过变量复用（如滚动变量）替代数组，最终目标是在不影响计算正确性的前提下，将空间复杂度从O(n²)降至O(n)或O(1)。06动态规划编程实战青蛙跳台阶问题代码实现最长递增子序列代码实现问题描述给定整数数组nums，找出其中最长严格递增子序列的长度。示例：输入[10,9,2,5,3,7,101,18]，输出4（对应子序列[2,3,7,101]）。动态规划解法定义dp[i]表示以nums[i]结尾的最长递增子序列长度。状态转移方程：dp[i]=max(dp[j]+1)，其中0≤j<i且nums[j]<nums[i]。边界条件：dp[0]=1，所有元素初始化为1。C++代码实现单击此处添加项正文07include<vector>#include<algorithm>usingnamespacestd;intlengthOfLIS(vector<int>&nums){if(nums.empty())return0;vector<int>dp(nums.size(),1);intmaxLen=1;for(inti=1;i<nums.size();++i){for(intj=0;j<i;++j){if(nums[j]<nums[i])dp[i]=max(dp[i],dp[j]+1);}maxLen=max(maxLen,dp[i]);}returnmaxLen;}二维数组基础实现定义dp[i][j]表示前i个物品在容量j下的最大价值，初始化(n+1)×(capacity+1)二维数组。状态转移方程：当物品重量≤j时，dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])；否则dp[i][j]=dp[i-1][j]。时间复杂度O(n×capacity)，空间复杂度O(n×capacity)。空间优化：一维数组实现使用滚动数组压缩空间，定义dp[j]表示容量j下的最大价值。从后往前遍历容量，状态转移方程：dp[j]=max(dp[j],dp[j-weight[i]]+value[i])。时间复杂度O(n×capacity)，空间复杂度优化至O(capacity)。Python代码示例defknapsack(weights,values,capacity):\nn=len(weights)\ndp=[0]*(capacity+1)\nforiinrange(n):\nforjinrange(capacity,weights[i]-1,-1):\n