动态规划是一种在数学、计算机科学和经济学中用于解决决策过程最优化问题的方法。它是通过将一个复杂问题分成若干个子问题，再通过对这些子问题的求解得到原问题的解的方法。
动态规划通常有两个步骤：状态转移和决策。
在状态转移步骤中，我们需要定义当前状态(如时间、地点、资源等)，并对状态进行分析，以确定下一步该如何转移。
决策步骤则是通过评估每种可能决策的结果，从而选择最优决策。
常见案例包括：
-
最长公共子序列问题：求两个序列的最长公共子序列的长度。
-
背包问题：在限定的容量内选择物品，使得总价值最大。
-
最短路径问题：求从一个点到另一个点的最短路径。
以最长公共子序列问题