算法笔记：从回溯到 DP 的优化之路

日期: 2026-03-10
主题: 记忆化搜索与动态规划
难度: Medium → Hard
标签: DP、记忆化搜索、状态转移、容斥原理

---

一、核心思想

记忆化的本质：把重复的子问题答案存起来，下次直接用。

关键问题：什么构成了一个唯一的状态？

优化路径

┌─────────────────────────────────────────────────┐
│  回溯 (暴力枚举)                                  
│  复杂度：O(2^n) 或 O(8^n) ❌                     
│  问题：大量重复计算                               
└─────────────────────────────────────────────────┘
                        ↓
┌─────────────────────────────────────────────────┐
│  记忆化搜索 (自顶向下)                            
│  复杂度：O(n × 状态数) ✅                        
│  关键：memo[状态]                                
└─────────────────────────────────────────────────┘
                        ↓
┌─────────────────────────────────────────────────┐
│  动态规划 (自底向上)                              
│  复杂度：O(n × 状态数) ✅                        
│  关键：dp[i][j] = f(dp[i-1][?])                  
└─────────────────────────────────────────────────┘

---

二、例题解析

📌 LeetCode 935. 骑士拨号器

题目链接: https://leetcode.cn/problems/knight-dialer/
难度: Medium
标签: DP、图论

题目描述

象棋骑士在电话垫上跳跃，给定整数 n，返回可以拨多少个长度为 n 的不同电话号码。

电话垫布局：

1 2 3
4 5 6
7 8 9
* 0 #

骑士只能站在数字单元格上，每次跳跃必须是有效的骑士跳跃（L 形）。

解题思路

关键洞察：

1. 无后效性：如果两条路径都到达数字 4，且都还剩 3 步要走，那么它们后续能走的路线完全一样。

2. 状态定义：dp[i][j] = 走 i 步后，停在数字 j 的路径数

3. 状态转移：从哪些数字能跳到当前数字

   0 → 4, 6
   1 → 6, 8
   2 → 7, 9
   3 → 4, 8
   4 → 0, 3, 9
   5 → (无)
   6 → 0, 1, 7
   7 → 2, 6
   8 → 1, 3
   9 → 2, 4

代码实现

class Solution {
public:
    int knightDialer(int n) {
        const int MOD = 1e9 + 7;
        
        // dp[i][j] = 走 i 步后，停在数字 j 的路径数
        vector<vector<long long>> dp(n, vector<long long>(10));
        
        // 初始化：走 0 步，每个数字都有 1 种方式（站在原地）
        for (int i = 0; i < 10; i++) {
            dp[0][i] = 1;
        }
        
        // 状态转移
        for (int i = 1; i < n; i++) {
            dp[i][0] = (dp[i-1][4] + dp[i-1][6]) % MOD;
            dp[i][1] = (dp[i-1][6] + dp[i-1][8]) % MOD;
            dp[i][2] = (dp[i-1][7] + dp[i-1][9]) % MOD;
            dp[i][3] = (dp[i-1][4] + dp[i-1][8]) % MOD;
            dp[i][4] = (dp[i-1][0] + dp[i-1][3] + dp[i-1][9]) % MOD;
            dp[i][6] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][7]) % MOD;
            dp[i][7] = (dp[i-1][2] + dp[i-1][6]) % MOD;
            dp[i][8] = (dp[i-1][1] + dp[i-1][3]) % MOD;
            dp[i][9] = (dp[i-1][2] + dp[i-1][4]) % MOD;
        }
        
        // 累加所有终点
        long long sum = 0;
        for (int i = 0; i < 10; i++) {
            sum = (sum + dp[n-1][i]) % MOD;
        }
        return sum;
    }
};

复杂度分析

维度	分析
时间	O(n × 10) = O(n)
空间	O(n × 10) = O(n)

空间优化（滚动数组）

// 用两个数组交替，空间 O(1)
vector<long long> dp(10, 1);

for (int i = 1; i < n; i++) {
    vector<long long> newDp(10);
    newDp[0] = (dp[4] + dp[6]) % MOD;
    newDp[1] = (dp[6] + dp[8]) % MOD;
    // ... 其他数字
    dp = newDp;
}

注意：空间优化不一定带来时间提升，这道题中频繁分配数组反而可能更慢。

---

📌 LeetCode 3130. 找出所有稳定的二进制数组 II

题目链接: https://leetcode.cn/problems/find-all-possible-stable-binary-arrays-ii/
难度: Hard
标签: DP、记忆化搜索、容斥原理

题目描述

给定三个正整数 zero、one 和 limit。一个二进制数组 arr 如果满足以下条件，称它是稳定的：

1. 0 在 arr 中出现次数恰好为 zero
2. 1 在 arr 中出现次数恰好为 one
3. arr 中每个长度超过 limit 的子数组都同时包含 0 和 1

返回稳定二进制数组的总数目，对 10^9 + 7 取余。

解题思路

关键洞察：

1. 条件 3 的等价转换：不能有连续超过 limit 个相同的数字

2. 状态定义：dfs(i, j, k) = 用 i 个 0 和 j 个 1 构造稳定数组的方案数，且数组末尾是 k（k=0 或 1）

3. 容斥原理（核心难点）：

   • 直接记录连续长度需要 O(limit) 维度
   • 用容斥减去非法情况，可以消除这个维度
   • 非法情况 = 末尾连续 limit+1 个相同数字

代码实现

class Solution {
public:
    int numberOfStableArrays(int zero, int one, int limit) {
        const int MOD = 1'000'000'007;
        
        // memo[i][j][k] = 用 i 个 0、j 个 1、末尾是 k 的方案数
        vector memo(zero + 1, vector<array<int, 2>>(one + 1, {-1, -1}));

        auto dfs = [&](this auto&& dfs, int i, int j, int k) -> int {
            // 递归边界
            if (i == 0) return k == 1 && j <= limit;  // 只剩 1
            if (j == 0) return k == 0 && i <= limit;  // 只剩 0
            
            int& res = memo[i][j][k];
            if (res != -1) return res;  // 记忆化
            
            if (k == 0) {
                // 末尾放 0：继续延长 0 串 + 从 1 转换 + 容斥减去非法
                res = ((long long)dfs(i-1, j, 0) + 
                       dfs(i-1, j, 1) +
                       (i > limit ? MOD - dfs(i-limit-1, j, 1) : 0)) % MOD;
            } else {
                // 末尾放 1：同理
                res = ((long long)dfs(i, j-1, 0) + 
                       dfs(i, j-1, 1) +
                       (j > limit ? MOD - dfs(i, j-limit-1, 0) : 0)) % MOD;
            }
            return res;
        };

        return (dfs(zero, one, 0) + dfs(zero, one, 1)) % MOD;
    }
};

状态转移详解

以 k == 0（末尾放 0）为例：

dfs(i, j, 0) = 
    dfs(i-1, j, 0)   // 前一个也是 0，继续延长
  + dfs(i-1, j, 1)   // 前一个是 1，0 串重新开始
  - dfs(i-limit-1, j, 1)  // 容斥：减去末尾连续 limit+1 个 0 的非法情况

为什么减去 dfs(i-limit-1, j, 1)？

• 非法情况 = 末尾恰好有 limit+1 个连续的 0
• 这等价于：前面用了 i-limit-1 个 0 和 j 个 1，且倒数第 limit+2 个位置必须是 1
• 所以非法方案数 = dfs(i-limit-1, j, 1)

复杂度分析

维度	分析
时间	O(zero × one)
空间	O(zero × one)

---

三、回溯 vs DP 对比

回溯版本（暴力）

// 骑士拨号器的回溯版本
void backtrack(string& path, int stepsLeft) {
    if (stepsLeft == 0) {
        ans++;
        return;
    }
    
    // 尝试 8 个方向
    for (auto& dir : dirs) {
        if (isValid()) {
            path.push_back(next);
            backtrack(path, stepsLeft - 1);
            path.pop_back();  // 回溯
        }
    }
}

问题：相同状态被重复计算无数次

DP 版本（优化）

// 只计算一次，存储结果
int dfs(int steps, int currentDigit) {
    if (memo[steps][currentDigit] != -1) 
        return memo[steps][currentDigit];
    
    int res = 0;
    for (auto& next : jumps[currentDigit]) {
        res = (res + dfs(steps - 1, next)) % MOD;
    }
    return memo[steps][currentDigit] = res;
}

---

四、关键总结

✅ 记忆化搜索的适用场景

1. 重叠子问题：不同路径会到达相同状态
2. 最优子结构：大问题的解可以由小问题的解推导
3. 状态可表示：能用有限的参数唯一确定一个状态

✅ 状态设计技巧

技巧	说明	例题
记录末尾元素	避免遍历历史	稳定二进制数组
用容斥消除维度	减少状态数	稳定二进制数组
预处理转移关系	加速状态转移	骑士拨号器

✅ 空间优化注意事项

优化优先级（面试场景）：
1. 时间复杂度优化（O(n²) → O(n)）← 最重要
2. 算法正确性 ← 基础
3. 代码可读性 ← 加分项
4. 空间复杂度优化 ← 锦上添花
5. 微优化（vector → 数组）← 竞赛才需要

核心原则：用清晰换几个 ms 的提速，不值得。面试中，清晰的代码会得分更高。

---

五、相关练习

题目	相似点	难度
70. 爬楼梯	最基础的状态转移	⭐
509. 斐波那契数	空间优化练习	⭐
1220. 统计元音字母序列	和骑士拨号器几乎一样	⭐⭐
935. 骑士拨号器	✅ 已完成	⭐⭐
3130. 稳定二进制数组 II	✅ 已完成	⭐⭐⭐