本文共 687 字，大约阅读时间需要 2 分钟。

动态规划基础知识

一、基本概念

动态规划是一种解决多阶段最优化决策问题的方法。每次决策都依赖于当前的状态，并随即引发状态的转移。这种基于阶段的最优化决策过程被称为动态规划。

二、基本思想与策略

动态规划的基本思想与分治法类似，通过将问题分解为若干子问题按顺序求解。每个子问题的解为下一个子问题提供有用信息。在求解每个子问题时，列出所有可能的局部解，保留那些可能达到最优的局部解，丢弃其他解。通过逐步解决各子问题，最终得到初始问题的最优解。

由于动态规划问题通常具有重叠子问题特性，为了减少重复计算，每个子问题的不同阶段的不同状态会被存储在一个二维数组中。

动态规划与分治法的主要区别在于：分解后的子问题往往不是独立的，而是有序的或可排序的，下一个子阶段的求解通常建立在上一个子阶段的解基础上。

三、适用的情况

动态规划适用于以下三个性质的问题：

四、求解的基本步骤

动态规划的设计通常包括以下几个步骤：

实际应用中，可以通过以下步骤设计动态规划：