换根 DP

**换根DP**

换根DP（Dynamic Programming）是一种常见的算法设计模式，用于解决复杂的问题。它通过分解问题为更小的子问题，并缓存这些子问题的答案，以避免重复计算，从而提高效率。

###什么是换根DP换根DP是一种基于状态转移方程的算法设计模式。它将原来的问题分解为多个子问题，每个子问题都有一个明确的状态和结果。通过缓存这些子问题的答案，我们可以避免重复计算，从而提高效率。

### 换根DP的步骤1. **定义状态**:首先，我们需要定义状态，这是换根DP中最重要的一步。状态通常是指当前处理的子问题。
2. **定义结果**:接下来，我们需要定义结果，这是指当前处理的子问题的答案。
3. **建立状态转移方程**:通过分析子问题之间的关系，我们可以建立状态转移方程。这是指从一个状态到另一个状态的过渡过程。
4. **缓存答案**:最后，我们需要缓存这些子问题的答案，以避免重复计算。

###代码示例下面是一个简单的换根DP例子，求出斐波那契数列中第 n 个数字：

def fibonacci(n):
 # 定义状态：dp[i] 表示斐波那契数列中的第 i 个数字 dp = [0] * (n +1)
 # 初始化状态：dp[0] 和 dp[1] 的值为0 和1 dp[0] =0 dp[1] =1 # 建立状态转移方程：dp[i] = dp[i-1] + dp[i-2]
 for i in range(2, n +1):
 dp[i] = dp[i -1] + dp[i -2]
 # 返回结果：斐波那契数列中的第 n 个数字 return dp[n]

# 测试代码print(fibonacci(10)) # 输出：55