概述
动态规划（Dynamic Programming，简称DP）是一种算法设计思想，用于解决具有重叠子问题和最优子结构性质的问题。它通过将复杂问题分解为较小的子问题，避免重复计算相同的子问题，从而提高计算效率。
基本思想可以概括为以下几个步骤：
- 定义子问题：将原问题分解为多个子问题。通常，子问题的解能够组合成原问题的解。
- 确认状态：定义问题的状态，一般通过一个或多个变量来描述当前的子问题。例如，在求解最长公共子序列的问题中，状态可以用两个变量来表示序列的长度。
- 状态转移方程：找出子问题之间的关系，即状态转移方程。这些方程描述了如何从一个或多个子问题的解得到原问题的解。
- 初始条件和边界情况：确定动态规划的初始条件，即最基本的子问题的解，以及边界情况。
- 求解和优化：通过迭代或递归方式求解所有子问题，得到最终的解。