软考-软件设计师：算法策略：动态规划法（用于求最优解）考的多-马育民老师

# 介绍

把大问题拆成 **重叠子问题**（重复的小问题），先算小问题，使用数组存储子问题结果，再一步步算出大问题。

>与贪心、分治法类似

# 审题技巧

如果提到 `最优子结构` 和 `递归式` 字样，说明是 `动态规划法`

# 实现方式

- 自顶向下

- 自底向上

# 实现方式一：自顶向下

**特点：**用到 **递归**

如：斐波那契

```
f(100) + f(99) + f(98) + f(97)  + ... + f(1)
```

**注意：**自顶向下，到底后，还要向上执行，所以时间复杂度比 `自底向上` 大

### 时间复杂度

$$O(2^n)$$

# 实现方式二：自底向上

**特点：**用到 **循环** + **数组**（一维、二维...）

如：计算二维数组的某种结果，需要用到双重循环

```
arr[0][0]
arr[0][1]
arr[0][2]
....
arr[m][n]
```

### 时间复杂度

$$O(n^a)$$ ( `a`：几重循环就是几)

# 经典问题

- 斐波那契数列
- 矩阵乘法
- 0-1背包问题（每个物品只有两种选择：装入背包或不装入背包）
- LCS最长公共子序列

# 斐波那契数列

### 自顶向下

```
# 自顶向下（记忆化递归）计算斐波那契
def fib_top_down(n, memo=None):
    # 初始化备忘录（第一次调用时创建）
    if memo is None:
        memo = {}  # 用字典存已经算过的结果，key是n，value是F(n)
    
    # 1. 递归终止条件（最小子问题）
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # 2. 先查备忘录：有就直接返回，不重复算
    if n in memo:
        return memo[n]
    
    # 3. 没有就递归计算，并存入备忘录
    res = fib_top_down(n-1, memo) + fib_top_down(n-2, memo)
    memo[n] = res  # 存结果，下次直接用
    
    return res

# 测试：计算第5个斐波那契数（结果应为5）
print(fib_top_down(5))  # 输出：5
# 测试：计算第10个斐波那契数（结果应为55）
print(fib_top_down(10)) # 输出：55
```
### 自底向上

```
# 动态规划计算斐波那契
def fib_dp(n):
    # 边界条件
    if n == 0:
        return 0
    if n == 1:
        return 1
    # 用数组存储子问题的解（避免重复计算）
    dp = [0] * (n+1)
    dp[0] = 0
    dp[1] = 1
    # 自底向上计算：先算小问题（F(2)），再算大问题（F(5)）
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# 计算F(5)
print(fib_dp(5))  # 输出：5
```

**特点：**每次算法都存起来

**分治法：**每次都重复计算，不会存起来

原文出处：http://malaoshi.top/show_1GW2lAm8571V.html