### 动态规划Python代码模板 动态规划通常用于解决具有最优子结构和重叠子问题的问题。基本的动态规划模板可以分为记忆化搜索（自顶向下）和递推（自底向上）两种方法。 #### 记忆化搜索（自顶向下） ```python memo = {} def dp(n): if n in memo: return memo[n] if n == base_case_condition: result = base_case_value else: # 状态转移方程 result = ... memo[n] = result return result ``` 在这个模板中，`memo`是一个字典，用于存储已经计算过的子问题的结果。`base_case_condition`是基本情况的判断条件，`base_case_value`是基本情况的结果。状态转移方程根据具体问题来确定。 #### 递推（自底向上） ```python # 初始化dp数组 dp = [0] * (n + 1) # 设置基本情况 dp[0] = base_case_value for i in range(1, n + 1): # 状态转移方程 dp[i] = ... # 返回最终结果 return dp[n] ``` 这里，`dp`数组用于存储子问题的结果，首先初始化基本情况，然后通过循环从基本情况开始逐步计算出所有子问题的结果，最后返回最终结果。状态转移方程同样需要根据具体问题进行确定。 ### 适用场景 动态规划适用于以下几类问题： 1. **优化问题**：如求最大值、最小值等。例如，背包问题就是求在给定容量下能装下的物品的最大价值；最长递增子序列问题是求一个序列中最长的递增子序列的长度。 2. **计数问题**：计算满足某些条件的方案数。例如，爬楼梯问题，计算到达第`n`级楼梯有多少种不同的方法。 3. **存在性问题**：判断是否存在满足某些条件的解。例如，判断是否可以从给定的数组中选择一些数，使得它们的和等于目标值。 ### 示例：斐波那契数列 斐波那契数列是一个经典的动态规划问题，其定义为：$F(n) = F(n - 1) + F(n - 2)$，其中$F(0) = 0$，$F(1) = 1$。 #### 记忆化搜索实现 ```python memo = {} def fib(n): if n in memo: return memo[n] if n == 0: result = 0 elif n == 1: result = 1 else: result = fib(n - 1) + fib(n - 2) memo[n] = result return result # 测试 print(fib(10)) ``` #### 递推实现 ```python def fib(n): if n == 0: return 0 dp = [0] * (n + 1) dp[0] = 0 dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n] # 测试 print(fib(10)) ```