动态规划实践报告一、动态规划概述动态规划（Dynamic Programming，DP）是一种通过将复杂问题分解为更小的子问题并存储子问题解来优化递归算法的算法设计技术它适用于具有以下特征的问题：1. 最优子结构：问题的最优解包含子问题的最优解2. 重叠子问题：不同递归路径中存在重复的子问题计算动态规划通常有两种实现方式：- 自顶向下（备忘录法）：通过递归计算并缓存子问题结果，避免重复计算 自底向上（表格法）：从最小子问题开始，逐层构建直到解决原问题二、动态规划应用场景动态规划适用于解决以下类型问题：（一）最优化问题1. 路径优化：如斐波那契数列、背包问题中的最大价值计算2. 长度计算：如最长公共子序列（LCS）问题二）计数问题1. 方案总数：如爬楼梯问题（每次可走1或2步，计算到达顶部的总方案数）2. 子序列统计：如统计特定序列中符合条件的子序列数量三）决策问题1. 最小成本路径：如网络路由中的最短路径计算2. 资源分配：如多阶段资源分配问题三、动态规划实现步骤（一）定义状态1. 明确问题的决策变量和状态表示 示例：背包问题中，状态dp[i][j]表示前i件物品在容量为j时的最大价值。
二）状态转移方程1. 建立当前状态与子状态的关系 示例：背包问题中，dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])三）初始条件与边界1. 确定最小子问题的解 示例：dp[0][j] = 0（无物品时价值为0），dp[i][0] = 0（容量为0时价值为0）四）计算顺序1. 自底向上时，确保子问题在当前层已被计算2. 自顶向下时，需按递归调用顺序缓存结果四、动态规划示例：背包问题（一）问题描述给定n件物品和一个容量为W的背包，物品i的重量为w[i]，价值为v[i]求背包能装载的最大总价值二）解决方案1. 状态定义：dp[i][j]表示前i件物品在容量j时的最大价值2. 状态转移：- 不选第i件：dp[i][j] = dp[i-1][j] 选第i件：dp[i][j] = dp[i-1][j-w[i]] + v[i]（若j ≥ w[i]）3. 初始条件：dp[0][j] = 0，dp[i][0] = 0三）时间与空间复杂度1. 时间复杂度：O(nW)，需计算所有状态2. 空间优化：可使用一维数组（滚动数组）将空间降至O(W)五、动态规划优化技巧（一）空间压缩1. 对于无后效性（当前状态仅依赖前一个状态）的问题，可减少存储维度。
示例：斐波那契数列使用变量交替存储替代二维数组二）剪枝优化1. 在递归中提前终止无望的分支 示例：搜索问题中排除不可能满足条件的路径三）记忆化搜索1. 通过哈希表缓存已计算状态，适用于树形递归问题六、总结动态规划通过分解子问题与缓存结果显著提升算法效率，尤其适用于组合优化问题关键步骤包括：明确状态定义、建立状态转移方程、设计计算顺序通过空间压缩与剪枝等技巧可进一步优化性能实际应用中需结合问题特性选择合适的实现方式一、动态规划概述动态规划（Dynamic Programming，DP）是一种重要的算法设计技术，主要用于解决具有特定结构的最优化问题其核心思想是将一个复杂问题分解为若干个相互关联的子问题，通过递归地求解这些子问题，并存储（记忆化）已解决子问题的结果，从而避免重复计算，最终高效地求解原问题动态规划特别适用于那些具有“最优子结构”和“重叠子问题”特征的问题1. 最优子结构 (Optimal Substructure)：这意味着一个问题的最优解包含了其子问题的最优解换句话说，如果一个问题可以通过组合其子问题的解来得到最优解，那么这个问题的最优子结构就得到了体现例如，在最优路径问题中，从起点到终点的最优路径，其包含的任意中间节点到终点的路径也必然是从该中间节点到终点的最优路径。
2. 重叠子问题 (Overlapping Subproblems)：在递归求解动态规划问题时，往往会反复计算许多相同的子问题如果这些问题在递归调用树中出现多次，就称为重叠子问题动态规划通过存储这些子问题的解（通常称为“备忘录”或“记忆化”），在后续需要时直接查表获取，避免了冗余的计算，从而提高了效率这与分治法不同，分治法中的子问题通常是独立的动态规划通常有两种主要的实现方式： 自顶向下（备忘录法，Top-Down with Memoization）：这种方法从原问题开始，通过递归函数进行求解在递归过程中，每遇到一个子问题，首先检查是否已经计算并存储了该子问题的解如果是，则直接返回存储的解；如果不是，则按常规递归方式计算该子问题，并将计算结果存储起来以备后续使用这种方法类似于带缓存功能的递归 实现步骤：(1) 定义递归函数，通常包含问题的状态参数2) 在函数内部，首先检查当前状态是否已存在于缓存（如字典或数组）中3) 如果存在，直接返回缓存值4) 如果不存在，递归计算子问题，并将结果存入缓存后返回 自底向上（表格法，Bottom-Up with Tabulation）：这种方法从最小的子问题开始，逐步计算并解决更大的子问题，直到最终解决原问题。
它通常使用一个数据结构（如一维或多维数组）来存储中间结果，这个数据结构被称为“DP表”或“表格”计算顺序严格按照状态依赖关系进行，确保在计算某个状态时，它所依赖的所有子状态都已被预先计算好 实现步骤：(1) 确定DP表的结构，通常根据状态参数的维度来设计（如一维数组、二维数组等）2) 初始化DP表，设置基础情况（边界条件），即最小子问题的解3) 按照特定的遍历顺序（通常是嵌套循环）遍历所有可能的状态4) 对于每个状态，根据状态转移方程，利用已计算好的子状态值来计算当前状态的值，并存储在DP表中5) 最终，DP表中存储的值即为原问题的解二、动态规划应用场景动态规划因其解决复杂优化问题的能力，在计算机科学和数学的许多领域都有广泛应用以下是一些典型的应用场景分类及实例：（一）最优化问题 (Optimization Problems)这类问题是动态规划最常见的应用领域，目标是在给定约束条件下找到最优的解（如最大值、最小值、最短路径等）1. 路径优化问题： 斐波那契数列：虽然简单，但其递归计算中存在大量重复调用 f(n-1) 和 f(n-2) 的情况，是动态规划（尤其是备忘录法）的经典教学案例。
直接递归的时间复杂度为 O(2^n)，而动态规划可通过存储中间结果将其优化到 O(n) 背包问题 (Knapsack Problem)：给定一组物品，每个物品有自己的重量和价值，背包有一个最大承重限制目标是选择一部分物品装入背包，使得在不超过背包承重的前提下，物品的总价值最大这是动态规划中最具代表性的问题之一 最长公共子序列 (Longest Common Subsequence, LCS)：给定两个序列，找到它们的最长子序列，该子序列在两个序列中都出现，但不要求连续例如，在序列 "ABCBDAB" 和 "BDCABB" 中，"BCAB" 是一个LCS 最长递增子序列 (Longest Increasing Subsequence, LIS)：给定一个序列，找到其中最长的子序列，该子序列的元素严格递增例如，在序列 [10, 9, 2, 5, 3, 7, 101, 18] 中，[2, 5, 7, 101] 或 [10, 101, 18] 都是LIS，长度为42. 资源分配问题： 多重背包问题：背包问题的一种变体，物品可以选取多个副本 生产与存储问题：给定生产成本、存储成本和需求预测，计划各阶段的生产量以最小化总成本。
二）计数问题 (Counting Problems)这类问题不追求最优解，而是计算满足特定条件的方案总数1. 爬楼梯问题：假设有 n 阶楼梯，每次可以走 1 阶或 2 阶，问共有多少种不同的走法到达楼顶？这是一个典型的动态规划计数问题，状态 dp[i] 表示到达第 i 阶的方法数，状态转移为 dp[i] = dp[i-1] + dp[i-2]2. 不同路径问题：在一个 m x n 的网格中，只能从左上角走到右下角，每次只能向右或向下移动问总共有多少条不同的路径？可以使用二维DP表，dp[i][j] 表示到达 (i, j) 的路径数，状态转移为 dp[i][j] = dp[i-1][j] + dp[i][j-1]3. 子集/组合计数：计算包含特定元素或满足特定大小条件的子集数量三）决策问题 (Decision Problems)这类问题需要在每一步做出选择，以影响最终结果1. 最优调度问题：例如，给定多个任务和它们的处理时间，需要在满足依赖关系和资源约束的前提下，安排任务执行顺序以最小化总完成时间（Makespan）2. 网络路由问题：在图中寻找一条从源节点到汇点的路径，使得某个成本函数（如距离、延迟）最小。
虽然Dijkstra算法通常使用贪心策略，但在某些变种或结合其他约束时，也可能用到动态规划的思路3. 棋盘路径问题：在棋盘上从起点到终点，每次只能移动特定格数（如国际象棋的马），计算所有可能的路径数量或最短路径长度三、动态规划实现步骤实现一个动态规划解决方案通常遵循以下系统化的步骤这些步骤将帮助清晰地构建算法，无论是采用自顶向下还是自底向上的方法一）定义状态 (Define the State)这是动态规划中最关键的一步，目标是明确子问题的表示一个好的状态定义应该能够：1. 明确子问题的输入和输出：状态应该能够清晰地描述一个子问题的范围或参数例如，在背包问题中，状态 (i, j) 很好地表示了前 i 件物品在容量为 j 时的最大价值2. 具有最优子结构：状态的定义应使得该状态的值可以通过其子状态的值来计算3. 包含所有必要信息：状态不能过于简化以至于丢失解决问题所需的信息，也不能过于复杂以至于难以计算 实践建议： 通常使用 `dp[i]`（一维数组）或 `dp[i][j]`（二维数组）等符号来表示状态 状态可以表示为“最大值”、“最小值”、“方案数”、“布尔值（是否可行）”等。
问自己：“如果要求解子问题 [某个范围/条件]，最核心的、需要计算的量是什么？”（二）找出状态转移方程 (Find the State Transition Equation)状态转移方程描述了当前状态如何由一个或多个先前状态推导出来它是动态规划的“核心规则”，规定了如何从已知信息计算未知信息1. 分析决策点：思考在达到当前状态的过程中，可能做了哪些决策导致了这个状态例如，在背包问题中，决策是“是否选择第 i 件物品”2. 建立递推关系： 如果选择了某个决策（如选择了第 i 件物品），那么当前状态的价值可能与哪个（或哪些）之前的子状态的价值有关？ 如果没有选择某个决策（如没有选择第 i 件物品），当前状态的价值又与哪个（或哪些）之前的子状态的价值有关？ 通常，状态转移方程会包含“取最大值”（求最优解）或“取最小值”、“求和”等操作3. 数学表达：将递推关系用数学公式表示出来例如，背包问题的转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j。