动态规划（Dynamic Programming，简称DP）算法是一种通过将问题划分为相互重叠的子问题，并解决子问题来解决原问题的方法。它通常用于优化问题，其中需要找到最优解或最大/最小值。动态规划算法的核心思想在于将复杂问题划分为可解决的子问题，通过递归或迭代的方式解决子问题，从而得到原问题的最优解。动态规划算法通常具有较高的时间复杂度，但通过合理的状态定义和状态转移方程设计，可以将问题的复杂度降低到可接受的范围内。
动态规划算法的一般步骤包括：定义子问题、构建状态转移方程、确定边界条件、解决子问题、记忆化或建表、求解原问题。其中，定义子问题是将原问题划分为若干子问题，这些子问题应具有最优子结构的特性，即原问题的最优解可以通过子问题的最优解推导出来。构建状态转移方程是通过观察子问题之间的关系，定义状态和状态之间的转移方式。边界条件是最简单的子问题的解，也就是递归或迭代的终止条件。解决子问题是按照定义的状态转移方程，从最简单的子问题开始逐步解决更复杂的子问题，直到解决原问题。记忆化或建表是为了避免重复计算，可以使用记忆化技术将子问题的解存储起来，或者使用表格/数组记录子问题的解。最后
