动态规划（Dynamic Programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学等领域中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划的核心思想是将复杂问题分解成若干个子问题，并存储子问题的解（通常用数组或哈希表等数据结构），当需要子问题的解时，可以直接查表获取，避免重复计算。
动态规划具有以下特点：
1. 最优子结构：一个问题的最优解包含其子问题的最优解。
2. 子问题重叠：子问题在求解过程中重复出现。
3. 无后效性：一旦某个给定子问题的解被确定后，它就不会被改变。
动态规划通常用于解决以下类型的问题：
最优化问题：例如，求最短路径、最长公共子序列等。
组合问题：例如，背包问题、棋盘覆盖问题等。
序列问题：例如，股票买卖问题、矩阵链乘问题等。
动态规划的基本步骤包括：
1. 定义状态：确定问题中的状态以及状态之间的关系。
2. 状态转移方程：建立状态之间的转移关系，即如何从子问题的解推导出原问题的解。
3. 边界条件：确定状态转移方程的初始条件和边界条件。
4. 求解顺序：确定求解子问题的顺序，通常是从最简单的子问题开始求解。
动态规划在解决实际问题中具有很高的效率，能够避免重复计算，节省时间资源。
