跳转至

线性 DP

线性 DP（Linear DP）

状态按照某个线性顺序（如数组下标）进行转移，每个状态只依赖于前面有限个状态。

  • 常见形式：dp[i] = f(dp[i-1], dp[i-2], ...)

  • 典型特征：

    • 状态：dp[i]
    • 转移：只从 dp[i-k] 转移
    • 顺序：从小到大递推

  • 通用模板:

    for i in range(起点, n):
    dp[i] = 根据前面的状态转移

经典问题 （爬楼梯）

爬楼梯

楼梯共 n 阶，每次可上 1 或 2 阶，一共有多少种爬法？

暴力递归

每一阶都有两种选择（走 1 阶或 2 阶），递归地枚举所有可能。

graph TD
    A["dp[9]"] --> B["dp[8]"]
    A --> C["dp[7]"]

    B --> D["dp[7]"]
    B --> E["dp[6]"]

    C --> F["dp[6]"]
    C --> G["dp[5]"]

    D --> H["dp[6]"]
    D --> I["dp[5]"]

    E --> J["dp[5]"]
    E --> K["dp[4]"]

    F --> L["dp[5]"]
    F --> M["dp[4]"]

    G --> N["dp[4]"]
    G --> O["dp[3]"]

    H --> H1["..."]
    H --> H2["..."]

    I --> I1["..."]
    I --> I2["..."]

    J --> J1["..."]
    J --> J2["..."]

    K --> K1["..."]
    K --> K2["..."]

    L --> L1["..."]
    L --> L2["..."]

    M --> M1["..."]
    M --> M2["..."]

    N --> N1["..."]
    N --> N2["..."]

    O --> O1["..."]
    O --> O2["..."]

    classDef pink fill:#ea69c0,color:#fff,stroke:#ea69c0;
    classDef red fill:#ea6b6b,color:#fff,stroke:#ea6b6b;
    classDef orange fill:#f28c52,color:#fff,stroke:#f28c52;
    classDef blue fill:#4aa3df,color:#fff,stroke:#4aa3df;
    classDef green fill:#7db67d,color:#fff,stroke:#7db67d;
    classDef cyan fill:#53c1b8,color:#fff,stroke:#53c1b8;
    classDef purple fill:#6f86e8,color:#fff,stroke:#6f86e8;

    class A pink;
    class B red;
    class C,D orange;
    class E,F,H blue;
    class G,I,J,L green;
    class K,M,N cyan;
    class O purple;
def climb(n: int) -> int:
    if n <= 2:
        return n

    # dp[i] = dp[i-1] + dp[i-2]
    return climb(n - 1) + climb(n - 2)

int climb(int n) {
    if (n <= 2)
        return n;

    // dp[i] = dp[i-1] + dp[i-2]
    return climb(n - 1) + climb(n - 2);
}

fn climb(n: i32) -> i32 {
    if n <= 2 {
        return n;
    }

    // dp[i] = dp[i-1] + dp[i-2]
    climb(n - 1) + climb(n - 2)
}
  • 时间复杂度：\(O(2^n)\)，存在大量重复计算
  • 空间复杂度：\(O(n)\)，递归栈深度

记忆化搜索

在暴力递归的基础上，用一个数组缓存已经计算过的结果，避免重复求解相同子问题。

flowchart TD
    A["dp[9]"] --> B["dp[8]"]
    A -.->|✂️| C["dp[7]"]

    B --> D["dp[7]"]
    B -.->|✂️| E["dp[6]"]

    D --> F["..."]
    D -.->|✂️| G["dp[5]"]

    F --> H["dp[3]"]
    F -.->|✂️| I["..."]

    H --> J["dp[2]"]
    H --> K["dp[1]"]

    %% 样式
    classDef green fill:#86b97f,stroke:#86b97f,color:#fff;
    classDef gray fill:#b3b3b3,stroke:#b3b3b3,color:#fff;
    classDef cut stroke:#ff4d4f,stroke-width:3px,stroke-dasharray: 5 5,color:#ff4d4f;

    class A,B,D,H,J,K green;
    class C,E,G,I gray;

    %% 给剪枝边加样式
    linkStyle 1 stroke:#ff4d4f,stroke-width:3px,stroke-dasharray: 5 5;
    linkStyle 3 stroke:#ff4d4f,stroke-width:3px,stroke-dasharray: 5 5;
    linkStyle 5 stroke:#ff4d4f,stroke-width:3px,stroke-dasharray: 5 5;
    linkStyle 7 stroke:#ff4d4f,stroke-width:3px,stroke-dasharray: 5 5;
def climb(n: int) -> int:
    memo = [-1] * (n + 1)

    def dfs(i: int) -> int:
        if i <= 2:
            return i
        if memo[i] != -1:
            return memo[i]
        memo[i] = dfs(i - 1) + dfs(i - 2)
        return memo[i]

    return dfs(n)

int climb(int n) {
    vector<int> memo(n + 1, -1);

    function<int(int)> dfs = [&](int i) -> int {
        if (i <= 2)
            return i;
        if (memo[i] != -1)
            return memo[i];
        return memo[i] = dfs(i - 1) + dfs(i - 2);
    };

    return dfs(n);
}

fn climb(n: usize) -> i32 {
    let mut memo = vec![-1; n + 1];

    fn dfs(i: usize, memo: &mut Vec<i32>) -> i32 {
        if i <= 2 {
            return i as i32;
        }
        if memo[i] != -1 {
            return memo[i];
        }
        memo[i] = dfs(i - 1, memo) + dfs(i - 2, memo);
        memo[i]
    }

    dfs(n, &mut memo)
}
  • 时间复杂度：\(O(n)\)，每个子问题只算一次
  • 空间复杂度：\(O(n)\)，递归栈 + 缓存数组

动态规划

将递归转为自底向上的递推，用 dp[i] 表示爬到第 i 阶的方案数。

\[ dp_i = dp_{i-1} + dp_{i-2} \]
flowchart LR
    A["dp[1]"] --> C["dp[3]"]
    B["dp[2]"] --> C

    B --> D["dp[4]"]
    C --> D

    C --> E["dp[5]"]
    D --> E

    D --> F["dp[6]"]
    E --> F

    E --> G["dp[7]"]
    F --> G

    F --> H["dp[8]"]
    G --> H

    G --> I["dp[9]"]
    H --> I

    %% 样式
    classDef green fill:#86b97f,stroke:#86b97f,color:#fff;
    class A,B,C,D,E,F,G,H,I green;
def climb(n: int) -> int:
    if n <= 2:
        return n

    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

int climb(int n) {
    if (n <= 2)
        return n;

    vector<int> dp(n + 1, 0);
    dp[1] = dp[2] = 1;

    for (int i = 3; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];

    return dp[n];
}

fn climb(n: usize) -> i32 {
    if n <= 2 {
        return n as i32;
    }

    let mut dp = vec![0; n + 1];
    dp[1] = 1;
    dp[2] = 2;

    for i in 3..=n {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    dp[n]
}
  • 时间复杂度：\(O(n)\)
  • 空间复杂度：\(O(n)\)

空间优化

本题的转移方程与斐波那契数列一致，只依赖于前两个状态 dp[i-1] 和 dp[i-2]。因此可以用两个变量滚动存储，空间优化为 O(1)，不需要额外数组。

def climb(n: int) -> int:
    if n <= 2:
        return n

    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b

    return b

int climb(int n) {
    if (n <= 2)
        return n;

    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        int tmp = b;
        b = a + b;
        a = tmp;
    }
    return b;
}

fn climb(n: i32) -> i32 {
    if n <= 2 {
        return n;
    }

    let (mut a, mut b) = (1, 2);
    for _ in 3..=n {
        let tmp = b;
        b = a + b;
        a = tmp;
    }
    b
}

复杂度对比总结

方法 时间复杂度 空间复杂度 特点
暴力递归 O(2^n) O(n) 重复计算
记忆化搜索 O(n) O(n) 自顶向下
动态规划 O(n) O(n) 自底向上
空间优化 DP O(n) O(1) 最优