动态规划（Dynamic Programming）是一种用于求解具有重叠子问题和最优子结构性质的问题的方法。它通常应用于多阶段决策过程或优化问题中，通过将复杂问题分解为简单的子问题来解决问题。
多阶段决策过程是指在一系列连续的阶段下进行决策的过程。每个阶段都有若干个可能的选择，并且每个选择都会产生一个特定的结果，这个结果又会作为下一个阶段输入的一部分。整个过程中，各阶段之间存在一定的关联性和依赖性。
假设我们有一个项目管理任务，需要完成一系列的任务（比如安装软件、编写文档等）。每个任务都有不同的开始时间和结束时间，以及各自的优先级和价值。目标是在有限的时间内，尽可能地提高项目的整体价值。
定义状态：在动态规划中，“状态”指的是一个子问题的解所依赖的信息。对于上述项目管理任务的例子来说，可以将“状态”定义为当前剩余时间以及已完成的任务的价值总和。
确定决策：每个状态下，可以选择进行或不进行某个任务。选择将影响未来各阶段的状态。
建立递归关系：找到当前状态与下一个状态之间的联系。即，如何从一个状态转换到另一个状态，并且计算每种情况下的最优解。
定义边界条件：确定初始状态和终止状态及其相应的价值或成本。
自底向上的求解方式：通过从小规模子问题开始逐步解决问题，避免重复计算相同的子问题，从而提高效率。这种方法也被称为备忘录方法（Memoization）。
假设我们有以下的任务列表及其相关信息：
| 任务 | 开始时间 | 结束时间 | 优先级 | 价值 |
|---|---|---|---|---|
| A | 0 | 2 | 3 | 15 |
| B | 2 | 4 | 6 | 20 |
| C | 4 | 6 | 7 | 25 |
| D | 6 | 8 | 5 | 30 |
设最大可用时间为 T，我们设定 T = 8。
dp[i] 表示在时间点 i 完成任务后的最大价值i < 0 或者 i > T 时，dp[i] = 0对于每个状态 dp[i]，可以通过选择或不选择当前阶段的任务来更新：
dp[i] = dp[i - 1]dp[i] = max(dp[i], value + dp[i - end_time])| 时间 i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| dp[i] | 0 | 0 | 0 | 15 | 20 | 25 | 30 | 35 | 40 |
在时间 T = 8 内，我们能够达到的最大项目价值为 40。
通过动态规划方法解决了上述项目管理任务的多阶段决策问题。这种方法将复杂的问题分解为简单的子问题，并且避免了重复计算相同的子问题，从而提高了算法效率。对于具有重叠子问题和最优子结构特性的多阶段决策过程，动态规划是一种非常有效的解决方案。