# 动态规划

## 目录
- [动态规划概念](#动态规划概念)
- [动态规划步骤](#动态规划步骤)
- [经典问题](#经典问题)
- [面试常见问题](#面试常见问题)

---

## 动态规划概念

### 定义

```java
// 动态规划：将问题分解为子问题
// 保存子问题的解，避免重复计算
// 自底向上求解
```

### 适用场景

```java
// 1. 最优子结构
// 2. 重叠子问题
// 3. 无后效性
```

---

## 动态规划步骤

### 步骤

```java
// 1. 定义状态
// 2. 状态转移方程
// 3. 初始状态
// 4. 计算顺序
```

---

## 经典问题

### 题1：斐波那契数列

```java
// 递归（低效）
public int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

// 动态规划
public int fibDP(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
```

### 题2：爬楼梯

```java
// 每次可以爬 1 或 2 步，有多少种方法
public int climbStairs(int n) {
    if (n <= 2) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
```

---

## 面试常见问题

### Q1: 动态规划的特点？

**答案：**
- 最优子结构
- 重叠子问题
- 自底向上求解

### Q2: 动态规划和递归的区别？

**答案：**
- **递归**：自顶向下，可能重复计算
- **动态规划**：自底向上，避免重复计算

---

*最后更新：2024年*
