动态规划问题

核心动态规划概念

动态规划解决方案通常涉及以下关键组成部分：

状态定义：定义 DP 数组/表中的每个元素代表什么
基本情况：为最简单的子问题初始化值
状态转移：定义如何从更小的子问题构建更大问题的解决方案的公式
实现方法：自下而上（制表法）或自顶向下（记忆化）

来源： problems/62.unique-paths.md60-98 problems/53.maximum-sum-subarray-cn.md110-136 problems/416.partition-equal-subset-sum.md142-180

常见的动态规划问题类型

仓库中的动态规划问题可以分为几种模式：

来源： problems/62.unique-paths.md60-70 problems/53.maximum-sum-subarray-cn.md37-110 problems/416.partition-equal-subset-sum.md47-52 problems/139.word-break.md44-60

状态定义和转移技术

状态定义和转移方程是任何动态规划解决方案的核心。以下是仓库中的常见模式示例：

一维 DP 数组

对于“最大子数组”等问题：

来源： problems/53.maximum-sum-subarray-cn.md110-136

二维 DP 数组

对于像“Unique Paths”这样的基于网格的问题：

来源： problems/62.unique-paths.md60-98 problems/63.unique-paths-ii.md52-70

实现方法

自底向上 (制表)

自下而上的方法从基本情况开始迭代地构建解决方案。

来源： problems/62.unique-paths.md129-152

自顶向下 (记忆化)

自顶向下的方法使用带缓存（记忆化）的递归。

来源： problems/62.unique-paths.md106-114

空间优化技术

许多 DP 解决方案可以优化以使用更少的内存。常见技术包括：

降维

将二维 DP 数组解决方案转换为一维。

来源： problems/62.unique-paths.md94-98 problems/416.partition-equal-subset-sum.md209-245

“Unique Paths”示例

来源： problems/62.unique-paths.md157-166

使用常数变量

对于某些问题，我们可以进一步优化，只使用常数个变量。

来源： problems/53.maximum-sum-subarray-cn.md379-387

经典动态规划问题

路径问题

“Unique Paths”和“Unique Paths with Obstacles”等基于网格的问题遵循一致的模式。

来源： problems/62.unique-paths.md60-70 problems/63.unique-paths-ii.md52-70

划分问题

涉及划分或子集选择的问题通常使用背包模式的变体。

来源： problems/416.partition-equal-subset-sum.md142-180

字符串问题

字符串上的动态规划需要不同的状态定义。

来源： problems/139.word-break.md60-95

解决动态规划问题的流程

在处理 DP 问题时，请遵循以下步骤：

确定 DP 是否适用:
- 寻找重叠子问题
- 检查是否存在最优子结构
定义状态:
- 我们需要什么信息来表示一个子问题？
- dp[i] 或 dp[i][j] 代表什么？
制定基本情况:
- 初始化最简单的情况
开发状态转移方程:
- 如何从更小的问题构建到更大的问题？
确定计算顺序:
- 自下而上还是自顶向下？
实现和优化:
- 空间和时间优化技术