动态规划（Dynamic Programming，简称DP）是一种在算法设计中使用的优化技术，主要用于解决具有重叠子问题和最优子结构性质的问题。这种方法通过将问题分解为更小的子问题，并存储这些子问题的解（通常使用一个表格或矩阵），以避免重复计算，从而提高效率。
核心概念
最优子结构：问题的最优解可以通过其构成子问题的最优解来推导。
重叠子问题：在求解原问题的过程中，相同的子问题会被多次计算。
工作原理
动态规划通过以下步骤工作：
定义状态：
确定问题的子问题，并定义表示这些子问题解的状态变量。
状态转移方程：
建立状态变量之间的关系，表达当前状态如何由之前的状态推导出来。
自底向上求解：
从最小的子问题开始，逐步构建出原问题的解。
应用场景
动态规划常用于求解最优化问题，如：
最长递增子序列
最小编辑距离
背包问题
优势
时间复杂度低：通过存储子问题的解，动态规划可以将指数级别的时间复杂度降低到多项式级别。
空间复杂度增加：为了存储子问题的解，动态规划可能会使用额外的空间，有时也被称为“带备忘录的递归”。
示例
以寻找数组中最长递增子序列的长度为例，动态规划算法会维护一个数组`memo`来存储已经计算过的子问题的解，避免重复计算。
```python
def L（nums, i）:
if i == 0:
return 1
if nums[i] in memo:
return memo[nums[i]]
memo[nums[i]] = 1 + max（L（nums, j） for j in range（i） if nums[j] < nums[i]）
return memo[nums[i]]
在这个例子中，`L`函数计算从数组`nums`的第`i`个元素开始的最长递增子序列的长度，`memo`字典用于存储已经计算过的结果。动态规划是解决复杂优化问题的一种强大工具，在计算机科学和运筹学领域有着广泛的应用