第10章 动态规划

第10章动态规划动态规划是一种非常重要的算法设计思想，它通过将复杂问题分解为多个子问题，并利用子问题的解来构建原问题的最优解。在本章中，我们将学习动态规划的基本概念、核心思想，并通过数字金字塔、股票买卖和01背包等经典问题来掌握其应用。10.1动态规划概述10.2典型例题10.301背包问题动态规划（DynamicProgramming，DP）是运筹学的重要分支，核心在于将复杂问题分解为子问题求解，与分治算法既有相似性又有本质区别。10.1动态规划概述引例：数字金字塔问题描述寻找一条从金字塔顶部到底部的路径，使路径上数字的和最大。贪心法的局限性贪心选择可能无法得到最优解，因为它无法证明当前选择是全局最优的。贪心法路径和为50，而最优路径和为62。数字金字塔与贪心法路径对比示意图核心思路：从顶向下分解问题，从底向上合并结果。分解过程：将原问题分解为求从下一行两个位置出发的最大路径和。合并过程：从最底层开始，逐步向上计算每个位置到底部的最大路径和，最终得到顶部的解。数字金字塔的求解过程数字金字塔的分解与合并过程示意图多阶段决策问题：决策过程可分为若干相互联系的阶段，每个阶段需要做出决策。状态：描述某个阶段子问题的变量集合，如dp[i][j]表示从第i行第j列出发的最大路径和。状态转移方程：描述状态之间关系的数学表达式，是动态规划的核心。例如：dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1])。10.1.2重要概念最优子结构：原问题的最优解包含子问题的最优解。这意味着我们可以通过求解子问题的最优解来构建原问题的最优解。无后效性：某阶段的状态一旦确定，后续决策不受之前状态和决策的影响。即未来与过去无关，只取决于当前状态。公共子问题：递归求解时会产生重复的子问题。动态规划通过记录子问题的解（记忆化）来避免重复计算，从而显著提升效率。10.1.3三大特征递归模式：从顶向下分解问题，将复杂的数字金字塔问题拆解为多个子问题，同时使用备忘录（Memoization）记录子问题的解，避免重复计算，提升算法效率。递推模式：从底向上合并结果，利用循环结构从金字塔的底层开始，逐步向上计算每个位置的最优状态值，最终推导出顶层的全局最优解。核心代码：分别实现递归（含备忘录）和递推两种模式的代码逻辑，对比两种实现方式的时间复杂度与空间复杂度差异。10.2.1数字金字塔程序实现10.2.2股票买卖问题问题描述已知n天中每一天股票的价格，在最多允许一次买卖的情况下，计算股票的最大利润。问题描述解题思路遍历每一天的价格，记录到当前为止的最低价格，并计算当前卖出的利润，更新最大利润。解题思路状态定义minPrice：记录最低价格maxProfit：记录最大利润状态定义一、问题描述在背包容量有限的情况下，选择物品装入背包，使总价值最大。这是一个经典的组合优化问题。二、问题分类1.01背包：每件物品只能选一次（要么选，要么不选）。2.完全背包：每件物品可以选无限次。3.多重背包：每件物品有有限的数量限制。10.301背包问题背包问题示意图问题描述：给定物品的重量和价值，以及背包容量，选择物品使总价值最大。解题思路：从最后一个物品开始考虑，对于每个物品，有选和不选两种选择。递归求解这两种选择的最优解，取较大者。分解过程：将问题分解为“选当前物品”和“不选当前物品”两个子问题。背包问题递归解法状态转移方程

：f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i])状态定义：f[i][v]表示前i件物品放入容量为v的背包的最大价值。背包问题递推解法使用递推法的解题过程，相当于在逐行填写如下表格。填写规则：要从第一行开始，从上向下逐行填写。使用f[i][v]代表第i行第v列上单元格的值，其计算公式为：f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i])背包问题递推解法优化在递推法时，计算下一行数据只用到上一行数据，因此可只记录一行数据填写规则：从上向下逐行填写。每一行从右向左逐列填写！计算公式：f[v]=max(f[v],f[v-w[i]]+c[i])核心知识回顾：课堂小结1.动态规划概述：掌握基本概念、核心思想及重叠子问题、最优子结构