动态规划是一种通过存储子问题解来优化重复计算的算法思想，适用于具有最优子结构和重叠子问题的问题，如斐波那契数列；在Python中可通过自底向上迭代法或自顶向下记忆化递归实现，前者利用列表保存状态逐步求解，后者借助缓存避免重复计算，显著提升效率。
动态规划（Dynamic Programming，简称DP）是一种解决复杂问题的算法思想，主要用于优化那些包含重复子问题和最优子结构的问题。Python 中实现动态规划算法，就是利用这种思想，通过将大问题拆解成小问题，并存储小问题的解来避免重复计算，从而提高效率。
什么是动态规划？
动态规划的核心是“记住已经算过的结果”。它适用于可以分解为多个相似子问题的情况，且这些子问题会重复出现。比如斐波那契数列：F(n) = F(n-1) + F(n-2)，直接递归会重复计算很多项，而用动态规划可以保存中间结果，显著提升性能。
动态规划通常有两个关键特征：
- 最优子结构：问题的最优解包含子问题的最优解。
- 重叠子问题：在求解过程中，相同的子问题会被多次调用。
动态规划的两种实现方式
在 Python 中，常用两种方式实现动态规划：
立即学习“Python免费学习笔记（深入）”；
1. 自底向上（迭代 + 表格法）
从最小的子问题开始，逐步计算并保存结果，直到解决原问题。通常使用数组或列表存储状态。
例如计算斐波那契数列第 n 项：
def fib(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
2. 自顶向下（递归 + 记忆化）
使用递归思路，但通过缓存（如字典或 @lru_cache 装饰器）保存已计算的结果，避免重复计算。
例如：
from functools import lru_cache@lru_cache(maxsize=None) def fib(n): if n <= 1: return n return fib(n-1) + fib(n-2)
常见应用场景
动态规划广泛用于以下类型的问题：
- 背包问题：在有限容量下选择物品使价值最大。
- 最长公共子序列（LCS）：找出两个字符串的最长公共部分。
- 爬楼梯问题：每次走1步或2步，有多少种走法。
- 股票买卖问题：设计交易策略获取最大利润。
基本上就这些。掌握动态规划的关键是识别问题是否具备子问题重叠和最优子结构，并学会定义状态和状态转移方程。在 Python 中写起来清晰简洁，适合初学者练习算法思维。不复杂但容易忽略细节。
