动态规划（Dynamic Programming）是一种解决问题的方法，它通常用于求解最优化问题。它的基本思想是将原问题分解成若干个子问题，以便更容易地求解，并且将子问题的解保存起来，以便重复使用。
动态规划算法通常包括以下步骤：
-
定义状态：将原问题划分为若干个子问题，并定义每个子问题的状态。
-
初始化状态：确定状态的初始值，通常是将问题规模较小的子问题的解作为初始值。
-
确定状态转移方程：找到将一个子问题转化为另一个子问题的递推关系式，以便通过已知子问题的解求出未知子问题的解。
-
计算最优解：计算每个子问题的解，并记录下来，以便重复使用。
-
根据子问题的解计算原问题的解。
常见的应用动态规划算法的问题包括背包问题、最长公共子序列、最长递增子序列、最大子段和、编辑距离等。这些问题都可以使用动态规划算法逐步求解，将问题划分为若干个子问题，并逐个求解这些子问题，最后得到原问题的最优解。
动态规划算法的优点是可以避免重复计算子问题，提高算法的效率，并且可以解决一些无法用贪心算法求解的问题。但是，该算法的缺点是需要额外的空间来存储子问题的解，同时也可能导致递归调用的深度过深，从而导致栈溢出等问题。