动态规划

动态规划 1. 核心思想 2. 基本步骤 3. 关键概念 3.1 基本概念 3.2 优化技巧

  1. 常见应用场景 5. 典型案例 5.1 斐波那契数列 5.2 背包问题 5.2.1 0-1背包问题 5.2.2 完全背包问题
    5.3 最短路径——Floyd算法 5.4 最长公共子序列（LCS） 5.5 最长递增子序列（LIS）
  2. 解题技巧与思路 7. 总结

动态规划

1. 核心思想

动态规划（Dynamic Programming, DP）是一种解决复杂问题的算法设计技术，适用于具有重叠子问题和最优子结构性质的问题。动态规划将问题分解成更小的子问题，通过解决这些子问题来解决原始问题。这种方法的关键在于避免重复计算。一旦解决了一个子问题，它的解就被存储起来，以便后续需要时直接使用，从而避免了重复计算。这种记忆化的技术称为“缓存”。

动态规划有两种主要实现方式：自顶向下的记忆化搜索（Top-down Memoization）和自底向上的迭代方法（Bottom-up Tabulation）。

实现方式 描述 优点 缺点 自顶向下（记忆化搜索）从目标问题出发，通过递归函数求解。遇到子问题时先检查缓存，已计算则直接返回结果，否则计算并缓存。 更符合直觉，代码结构与递归定义相似 可能因递归深度过大导致栈溢出 自底向上（迭代法/状态表法）从最小子问题开始，按顺序计算并填充状态表，直到解决目标问题 避免递归开销，效率更高，不易栈溢出 需要明确计算顺序 ### 2. 基本步骤

划分阶段：将原问题按顺序分解为若干阶段，每个阶段对应一个子问题 定义状态：用变量描述子问题的特征，设计状态表示（状态设计要满足无后效性） 状态转移方程：根据前一阶段的状态和决策，推导出当前阶段的状态 初始条件和边界条件：根据问题描述和状态定义，确定初始状态和边界 计算顺序：通常按阶段递推，最终得到目标问题的解

3. 关键概念

3.1 基本概念

最优子结构：问题的最优解包含其子问题的最优解 重叠子问题：子问题会被多次计算，可通过记忆化避免重复计算 无后效性：某阶段状态一旦确定，之后的决策不再受此前各状态及决策的影响

3.2 优化技巧

状态压缩：当状态转移只依赖有限几个阶段的状态时，可优化存储方式降低空间复杂度 滚动数组：例如，计算斐波那契数列时，dp[i]只依赖dp[i-1]和dp[i-2]，只需存储这两个值 维度压缩：对于二维DP，如果dp[i][j]只依赖dp[i-1][...]，可将二维数组压缩为一维数组 例如：0-1背包问题的空间可从O(N*W)优化到O(W)

4. 常见应用场景

序列型问题：最长递增子序列、最长公共子序列、编辑距离 背包问题：0-1背包、完全背包、多重背包 区间型问题：最长回文子串、矩阵链乘法 坐标型问题：矩阵路径、不同路径数 博弈型问题：石子游戏、Nim游戏 状态压缩DP：使用二进制表示状态的DP问题 树形DP：在树结构上的动态规划 图论问题：最短路径（如Floyd算法） 股票问题：含冷冻期、交易次数限制等变种

5. 典型案例

5.1 斐波那契数列

问题描述：求第n个斐波那契数。

状态设计：f[i]表示第i个斐波那契数。

状态转移方程：f[i] = f[i-1] + f[i-2]

初始条件：f[0]=0, f[1]=1

代码示例（C语言）：

#include 
#include 

// 迭代法实现斐波那契数列计算
int fib(int n) {
    if(n