动态规划深度解析笔记

导论：动态规划的核心思想

动态规划（DP）并非一种特定的算法，而是一种解决问题的思维方式。它通常用于求解最优化问题（求最大值、最小值、最优策略），可行性问题（判断是否存在解）或计数问题（求解方案总数）。

要使用动态规划，一个问题必须具备两个核心特性：

1. 最优子结构 (Optimal Substructure): 问题的最优解可以由其子问题的最优解有效地构造出来。这意味着我们可以将原问题分解成规模更小、结构相同的子问题。

2. 重叠子问题 (Overlapping Subproblems): 在问题的求解过程中，许多子问题的解会被重复计算多次。DP通过存储（记忆化）这些子问题的解来避免重复计算，从而提高效率。

DP的两种思维模型

在深入学习具体DP类型之前，建立两种宏观的思维模型至关重要：

1. 优化型DP:
   • 目标: 求解一个全局的最优值（最大、最小、最长等）。
   • 状态定义: dp[...] 通常代表一个数值，如“最大价值”、“最短路径”、“最长长度”。
   • 思维模式: 像是在爬山，每一步都基于之前所有可能路径中的“最佳点”来决定当前这一步的最优值。经典例子如背包问题、最长递增子序列。
2. 状态机DP:
   • 目标: 求解可行性（是/否）或方案总数。
   • 状态定义: dp[...] 通常代表一个布尔值（是否可达）或计数值（有多少种方式可达）。
   • 思维模式: 像是在走一个迷宫或有限状态自动机。我们不关心路径的“优劣”，只关心“能否从某个特定状态走到另一个特定状态”。状态之间的转移关系是严格且固定的。经典例子如本文档中的“兔子问题”。

本笔记将从问题结构的角度，详细剖析动态规划的各大主流类型。

---

一、线性DP

线性DP是动态规划中最基础、最常见的一种类型。它的状态转移是线性的，通常沿着序列、数组或网格等一维或二维结构进行。

1. 核心思想

线性DP的状态通常定义在序列的前 i 个元素上。dp[i] 的值依赖于 dp[i-1], dp[i-2], ... 等在 i 之前的状态。状态的维度通常是一维或二维。

2. 特点与适用场景

• 适用场景:
  • 问题建立在一个线性结构上，如数组、字符串。
  • 问题的解具有明显的阶段性，处理完第 i 个阶段后，决策只与前面的阶段有关。
• 优点:
  • 模型相对简单，容易理解和实现。
  • 是学习其他复杂DP类型的基础。
• 缺点/挑战:
  • 状态定义和转移方程需要仔细设计，微小的差异可能导致完全错误的结果。
  • 当数据范围较大时，朴素的线性DP可能会超时，需要结合其他数据结构或算法进行优化（如斜率优化、数据结构优化等）。

3. 经典范例：0/1背包问题

问题描述

有 N 件物品和一个容量为 W 的背包。第 i 件物品的重量是 weight[i]，价值是 value[i]。求解将哪些物品装入背包，可使这些物品的重量总和不超过背包容量，且价值总和最大。
每件物品只能用一次（放或不放）。

分析与思路

1. 为什么是DP问题？
   • 最优子结构: 考虑前 i 个物品的最优解。这个解，要么包含了第 i 个物品，要么不包含。
     • 如果不包含第 i 个物品，那么最优解就是“在前 i-1 个物品中，放入容量为 W 的背包”的最优解。
     • 如果包含第 i 个物品，那么最优解就是“在前 i-1 个物品中，放入容量为 W - weight[i] 的背包”的最优解，再加上 value[i]。
       这表明，大问题的最优解依赖于小问题的最优解。
   • 重叠子问题: 在递归求解过程中，"考虑前k个物品，容量为w" 这样的子问题会被反复遇到。
2. 状态定义
   我们需要两个维度来描述一个子问题：“考虑到了哪个物品”和“当前背包剩余容量是多少”。
   因此，定义 dp[i][j] 为：从前 i 个物品中任意选择，放入容量为 j 的背包中所能获得的最大价值。

3. 状态转移方程
   对于第 i 个物品，我们有两种选择：

   • 不放入背包: 如果我们不把第 i 个物品放入背包，那么 dp[i][j] 的值就等于只考虑前 i-1 个物品放入容量为 j 的背包的最大价值。即：
     dp[i][j] = dp[i-1][j]
   • 放入背包: 如果我们决定放入第 i 个物品，前提是当前背包容量 j 必须大于等于 weight[i]。放入后，背包的剩余容量为 j - weight[i]。我们需要用这个剩余容量去装前 i-1 个物品，并获得最大价值。即：
     dp[i][j] = dp[i-1][j - weight[i]] + value[i]

   综合两种情况，我们要取其中的最大值，所以最终的转移方程为：
   dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i]) (需满足 j >= weight[i])

4. 初始化 (Base Case)

   • dp[0][...]：当一个物品都不考虑时，无论背包容量多大，最大价值都是0。所以 dp[0][j] = 0。
   • dp[...][0]：当背包容量为0时，什么也装不下，最大价值也是0。所以 dp[i][0] = 0。
   • 通常，我们可以将整个 dp 表初始化为0。
5. 最终答案
   我们要求的是从前 N 个物品中选择，放入容量为 W 的背包的最大价值，所以最终答案是 dp[N][W]。

C++ 实现 (空间优化版)

朴素的二维实现需要 O(N*W) 的空间。可以发现，dp[i] 的计算只依赖于 dp[i-1]，因此可以用滚动数组或一维数组进行优化。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int knapsack_01(const vector<int>& weights, const vector<int>& values, int W) {
    int N = weights.size();
    // dp[j] 表示容量为 j 的背包能获得的最大价值
    vector<int> dp(W + 1, 0);

    // 遍历每个物品
    for (int i = 0; i < N; ++i) {
        // 必须从后往前遍历，保证每个物品只用一次
        // 如果从前往后，dp[j-w] 会被当前物品 i 更新，导致物品 i 被重复使用
        for (int j = W; j >= weights[i]; --j) {
            // 决策：放或不放物品 i
            // 不放: dp[j] 的值保持不变
            // 放: dp[j] 的值更新为 dp[j - weights[i]] + values[i]
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }

    return dp[W];
}

int main() {
    vector<int> weights = {1, 2, 3};
    vector<int> values = {60, 100, 120};
    int W = 5;
    int max_value = knapsack_01(weights, values, W);
    cout << "最大价值是: " << max_value << endl; // 输出: 220
    return 0;
}

复杂度分析

• 时间复杂度: O(N * W)，因为有两个嵌套循环，分别遍历物品和容量。
• 空间复杂度: 朴素版为 O(N * W)，优化后为 O(W)。

---

二、区间DP

区间DP是一类在线性结构上进行DP的特殊模型，它通常用于解决与“连续子区间”的最优性质相关的问题。

1. 核心思想

区间DP的特征是，一个大区间 [i, j] 的最优解，可以通过枚举该区间内的一个“分割点” k，由两个或多个小区间（如 [i, k] 和 [k+1, j]）的最优解合并而来。它的计算顺序通常是先计算长度为1的区间，然后是长度为2的区间，以此类推，直到计算出整个区间的解。

2. 特点与适用场景

• 适用场景:
  • 问题求解的目标是针对一个序列的某个最优值。
  • 问题的最优解具有可合并性，即大区间的解可以由小区间的解推导出来。
  • 状态转移不依赖于区间外的元素。
• 优点:
  • 模型相对固定，代码结构通常是“三层循环”：第一层枚举区间长度，第二层枚举区间起点，第三层枚举分割点。
• 缺点/挑战:
  • 时间复杂度通常较高，至少是 O(N^3)，其中 N 是序列长度。
  • 状态转移方程的合并（merge）操作需要根据题意精心设计。

3. 经典范例：石子合并

问题描述

在一个圆形操场的四周摆放着 N 堆石子，现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。求将 N 堆石子合并成一堆的最小总得分。

分析与思路

1. 问题转化:
   圆形操场的问题不好处理，可以将其“断环成链”。我们将 N 堆石子的序列复制一遍接在后面，形成一个长度为 2N-1 的链。这样，原问题中任意一个长度为 N 的连续子段，都对应了原圆形操场上的一种断开方式。我们只需求出这个长链上所有长度为 N 的子区间的最小合并得分，再取其中的最小值即可。

2. 状态定义
   我们关心的是将某一个“区间”内的石子合并成一堆的最小得分。
   定义 dp[i][j] 为：将区间 [i, j] 内的石子合并成一堆的最小得分。
   为了计算合并得分，我们还需要知道区间的石子总数。可以用前缀和 sum[i] 快速计算 sum(i, j) = sum[j] - sum[i-1]。

3. 状态转移方程
   要计算 dp[i][j]，我们可以考虑区间 [i, j] 的最后一次合并。这次合并必然是由两个相邻的小堆合并而成的。这两个小堆是由 [i, k] 和 [k+1, j] 区间内的石子分别合并而成的（其中 i <= k < j）。

   • 将 [i, k] 合并的最小得分为 dp[i][k]。
   • 将 [k+1, j] 合并的最小得分为 dp[k+1][j]。
   • 将这两堆合并的得分为 sum(i, j)。

   所以，通过分割点 k 进行合并的总得分为 dp[i][k] + dp[k+1][j] + sum(i, j)。
   我们需要枚举所有可能的分割点 k，取其中的最小值。
   dp[i][j] = min(dp[i][k] + dp[k+1][j]) + sum(i, j) (对于 i <= k < j)

4. 初始化 (Base Case)

   • dp[i][i]：区间长度为1，只有一堆石子，不需要合并，所以得分为0。dp[i][i] = 0。
   • dp 表的其他值可以初始化为无穷大。
5. 最终答案
   对于断开成的长链，我们要求的是所有长度为 N 的区间的最小值，即 min(dp[i][i+N-1]) for 1 <= i <= N。

C++ 实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

int merge_stones(const vector<int>& stones) {
    int n = stones.size();
    if (n <= 1) {
        return 0;
    }

    // 断环成链
    vector<int> a(2 * n);
    for (int i = 0; i < 2 * n; ++i) {
        a[i] = stones[i % n];
    }
    int N = 2 * n;

    // 计算前缀和 (索引从1开始)
    vector<int> s(N + 1, 0);
    for (int i = 0; i < N; ++i) {
        s[i + 1] = s[i] + a[i];
    }

    auto get_sum = [&](int i, int j) {
        return s[j + 1] - s[i];
    };

    // dp[i][j] 表示合并 a[i...j] 的最小得分
    vector<vector<int>> dp(N, vector<int>(N, INF));

    // 初始化：长度为1的区间不需要合并
    for (int i = 0; i < N; ++i) {
        dp[i][i] = 0;
    }

    // 枚举区间长度，从 2 到 n
    for (int length = 2; length <= n; ++length) {
        // 枚举区间起点 i
        for (int i = 0; i <= N - length; ++i) {
            int j = i + length - 1;
            // 枚举分割点 k
            for (int k = i; k < j; ++k) {
                int cost = dp[i][k] + dp[k + 1][j] + get_sum(i, j);
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }

    // 在所有长度为 n 的区间中找最小值
    int min_score = INF;
    for (int i = 0; i < n; ++i) {
        min_score = min(min_score, dp[i][i + n - 1]);
    }

    return min_score;
}

int main() {
    vector<int> stones = {4, 5, 9, 4};
    cout << "最小得分为: " << merge_stones(stones) << endl; // 输出: 43
    return 0;
}

复杂度分析

• 时间复杂度: O(N^3)，来自三层循环（长度、起点、分割点）。
• 空间复杂度: O(N^2)，用于存储 dp 表和前缀和数组。

---

三、树形DP

树形DP是在树这种非线性结构上进行动态规划的一类问题。它利用了树的递归结构，通常通过深度优先搜索（DFS）来实现状态的计算和转移。

1. 核心思想

树形DP的求解过程通常是一个后序遍历。对于一个节点 u，我们先递归地处理它的所有子节点 v，计算出子节点的相关DP值。然后，利用这些子节点的DP值来计算节点 u 自身的DP值。这个过程从叶子节点开始，信息逐层向上传递，直到根节点。

2. 特点与适用场景

• 适用场景:
  • 问题建立在树状结构上。
  • 问题的解可以通过子树的解合并得到。
  • 通常不涉及环路。
• 优点:
  • 能够优雅地解决很多图论问题，特别是当图是一棵树时。
  • 代码结构清晰，通常是DFS的框架内嵌DP状态转移。
• 缺点/挑战:
  • 状态定义可能比较复杂，有时需要多个维度来表示节点的不同状态。
  • 对于带环的图，需要先用其他算法（如Tarjan缩点）处理环，才能应用树形DP。

3. 经典范例：树的最大独立集

问题描述

给定一棵 N 个节点的树，在树上选择一些节点，使得任意两个被选择的节点之间没有边相连。求最多能选择多少个节点。

分析与思路

1. 状态定义
   对于树上的任意一个节点 u，它只有两种状态：被选中或不被选中。这两种选择会影响其子节点的决策。
   • 如果 u 被选中，那么它的所有直接子节点都不能被选中。
   • 如果 u 不被选中，那么它的每个直接子节点都可以自由选择（既可以被选中，也可以不被选中），我们取其最优情况即可。

   因此，我们定义 dp[u][state] 为：

   • dp[u][1]: 在以 u 为根的子树中，选择节点 u 的情况下，能得到的最大独立集大小。
   • dp[u][0]: 在以 u 为根的...

   C++ 实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> adj[100005];
int dp[100005][2]; // dp[u][0]: 不选u, dp[u][1]: 选u

void dfs(int u, int parent) {
    // 初始化当前节点
    dp[u][1] = 1; // 选自己
    dp[u][0] = 0; // 不选自己

    for (int v : adj[u]) {
        if (v == parent) {
            continue;
        }

        // 递归处理子节点
        dfs(v, u);

        // 状态转移
        // 如果选 u，子节点 v 必须不选
        dp[u][1] += dp[v][0];
        // 如果不选 u，子节点 v 可以选也可以不选，取最优
        dp[u][0] += max(dp[v][0], dp[v][1]);
    }
}

int main() {
    // 示例: 树结构: 1 -- 2, 1 -- 3, 2 -- 4, 2 -- 5
    int n = 5;
    vector<pair<int, int>> edges = {{1, 2}, {1, 3}, {2, 4}, {2, 5}};

    for (const auto& edge : edges) {
        adj[edge.first].push_back(edge.second);
        adj[edge.second].push_back(edge.first);
    }

    // 从任意节点开始DFS，比如节点1
    dfs(1, 0);

    // 最终答案是根节点的两种选择中的最优解
    int result = max(dp[1][0], dp[1][1]);
    cout << "最大独立集大小为: " << result << endl; // 输出: 3 (选择 3, 4, 5)

    return 0;
}

复杂度分析

• 时间复杂度: O(N)，因为DFS会访问每个节点和每条边恰好一次。
• 空间复杂度: O(N)，用于存储邻接表、dp 数组以及DFS的递归栈深度。

---

四、状态压缩DP

状态压缩DP是一种特殊的DP技巧，它通过将一个复杂的状态（通常是一个集合）用一个整数的二进制位来表示，从而解决了状态空间过大的问题。

1. 核心思想

当DP的某一维度需要表示一个元素集合（例如，“哪些城市已经被访问过”），并且这个集合的大小 N 不太大（通常 N <= 20）时，我们可以用一个 N 位的二进制数（位掩码 bitmask）来表示这个集合。整数的第 i 位是 1 表示集合中包含第 i 个元素，为 0 表示不包含。这样，原本无法直接存入数组的状态，就被“压缩”成了一个整数索引。

2. 特点与适用场景

• 适用场景:
  • 问题涉及到一个小规模集合的所有子集或排列。
  • DP状态需要记录一个“集合”信息。
  • 数据规模 N 很小，使得 2^N 在可接受范围内。
• 优点:
  • 能够解决一些看似是指数级搜索的问题。
  • 将集合操作转化为高效的位运算（&, |, ^, <<, >>）。
• 缺点/挑战:
  • 受限于数据规模 N，当 N 稍大时，2^N 会迅速爆炸，导致时间和空间都无法承受。
  • 状态转移的逻辑可能比较复杂，需要熟练掌握位运算。

3. 经典范例：旅行商问题 (TSP)

问题描述

给定 N 个城市和一个表示城市之间距离的邻接矩阵 dist[i][j]。一个旅行商从某个城市出发，需要访问所有其他城市恰好一次，最后回到出发城市。求最短的旅行路径长度。

分析与思路

1. 状态定义
   我们需要记录两个关键信息：“当前已经访问过的城市集合”和“当前所在的城市”。
   • “访问过的城市集合”可以用一个位掩码 mask 来表示。
   • “当前所在的城市”可以用一个整数 i 表示。

   因此，定义 dp[mask][i] 为：在访问了 mask 所代表的城市集合，且当前停留在城市 i 的情况下，已经走过的最短路径长度。
   这里要求 mask 的第 i 位必须是 1。

2. 状态转移方程
   我们要计算 dp[mask][i]。可以考虑上一步是从哪个城市 j 来到城市 i 的。
   如果上一步在城市 j，那么当时的状态应该是：访问了 mask 中除 i 以外的所有城市，且停留在 j。这个状态对应的 mask 是 mask ^ (1 << i)（从 mask 中去掉 i）。
   所以，从城市 j 转移到城市 i 的路径长度为 dp[mask ^ (1 << i)][j] + dist[j][i]。

   我们需要枚举所有可能的上一个城市 j（j 必须在 mask 中且 j != i），并取其中的最小值。
   dp[mask][i] = min(dp[mask ^ (1 << i)][j] + dist[j][i]) (对于所有 j 满足 (mask >> j) & 1 且 j != i)

3. 初始化 (Base Case)

   • 假设我们从城市 0 出发。旅行开始时，只访问了城市 0，停留在城市 0，路径长度为0。
     dp[1 << 0][0] = 0。
   • dp 表的其他值初始化为无穷大。
4. 最终答案
   当所有城市都被访问过时，mask 变为 (1 << N) - 1（即所有位都是1）。此时，我们需要从各个可能的终点城市 i 回到起点城市 0。
   所以，最终答案是 min(dp[(1 << N) - 1][i] + dist[i][0]) (对于 1 <= i < N)。

C++ 实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max() / 2; // 防止溢出

int tsp(int n, const vector<vector<int>>& dist) {
    // dp[mask][i]: 访问集合为 mask，当前在城市 i 的最短路径
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));

    // 初始化：从城市 0 出发
    dp[1][0] = 0;

    // 枚举所有状态 mask
    for (int mask = 1; mask < (1 << n); ++mask) {
        // 枚举当前城市 i
        for (int i = 0; i < n; ++i) {
            // 如果当前城市 i 不在集合 mask 中，跳过
            if (!((mask >> i) & 1)) {
                continue;
            }

            // 枚举上一个城市 j
            for (int j = 0; j < n; ++j) {
                // 如果上一个城市 j 也在集合 mask 中，且 j != i
                if (i != j && ((mask >> j) & 1)) {
                    int prev_mask = mask ^ (1 << i);
                    // 状态转移
                    if (dp[prev_mask][j] != INF) {
                        dp[mask][i] = min(dp[mask][i], dp[prev_mask][j] + dist[j][i]);
                    }
                }
            }
        }
    }

    // 计算最终结果：从所有终点回到起点 0
    int final_mask = (1 << n) - 1;
    int min_path = INF;
    for (int i = 0; i < n; ++i) {
        if (dp[final_mask][i] != INF) {
            min_path = min(min_path, dp[final_mask][i] + dist[i][0]);
        }
    }

    return min_path;
}

int main() {
    int n = 4;
    vector<vector<int>> dist = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    cout << "最短旅行路径长度为: " << tsp(n, dist) << endl; // 输出: 80
    return 0;
}

复杂度分析

• 时间复杂度: O(N^2 * 2^N)。mask 有 2^N 种，i 和 j 分别有 N 种。
• 空间复杂度: O(N * 2^N)，用于存储 dp 表。

---

五、数位DP

数位DP是一类用于解决特定区间 [L, R] 内，满足某种与“数位”相关的性质的数字个数的计数问题。

1. 核心思想

直接在 [L, R] 区间上计数很困难。数位DP通过一个转换 count(R) - count(L-1) 来求解。核心是实现 count(X) 函数，它计算 [1, X] 区间内满足条件的数的个数。

count(X) 的实现方式是按位进行DP。我们将数字 X 转化为字符串，从最高位向最低位进行构造。DP过程中需要记录当前构造到的位数、当前状态（如各位数字之和、是否出现过某个数字等），以及一些关键的约束标记。

2. 特点与适用场景

• 适用场景:
  • 问题要求统计一个大区间内满足“数位”性质的数的个数。
  • “数位”性质只与数字本身的组成有关，与其他数无关（例如：不含数字4，各位数字和是10的倍数等）。
• 优点:
  • 能够解决在暴力枚举下会超时的计数问题。
  • 模型相对固定，通常是记忆化搜索的实现形式。
• 缺点/挑战:
  • 状态设计比较复杂，需要仔细考虑所有影响后续决策的因素，并将其加入DP状态。
  • 边界条件（is_limit）和前导零（is_leading_zero）的处理容易出错。

3. 经典范例：统计不含“49”的数字个数

问题描述

给定一个区间 [L, R]，求其中有多少个数不包含连续的数字“49”。

分析与思路

1. 实现 solve(X) 函数: solve(X) 计算 [0, X] 之间不含“49”的数的个数。最终答案是 solve(R) - solve(L-1)。

2. 记忆化搜索框架: 我们用一个递归函数 dfs(pos, prev_digit, is_limit, is_leading_zero) 来实现。

   • pos: 当前正在处理从左到右的第几位。
   • prev_digit: 前一位填的数字是什么（用于判断是否构成“49”）。
   • is_limit: 一个布尔标记，表示当前位能够填写的数字是否受到 X 对应位的限制。例如，X=567，我们在处理百位时，如果填了 1, 2, 3, 4，那么后面的十位和个位就可以任意填 0-9 (is_limit 变为 false)；但如果百位填了 5，那么十位最多只能填到 6 (is_limit 保持 true)。
   • is_leading_zero: 一个布尔标记，表示当前是否处于前导零阶段。例如，对于 567，我们在百位填 0 是无效的，这其实是在构造一个两位数。is_leading_zero 为 true 时，prev_digit 不起作用。
3. 状态定义与转移:
   dp[pos][prev_digit] 存储在没有限制的情况下，从 pos 位开始构造，且前一位是 prev_digit 时，合法的方案数。
   在 dfs 函数内部：
   • 递归出口: 如果 pos 超出了数字的长度，说明成功构造了一个合法的数，返回 1。
   • 记忆化: 如果 is_limit 为 false 且 is_leading_zero 为 false，并且 dp[pos][prev_digit] 已经被计算过，直接返回结果。
   • 循环: 枚举当前位 pos 可以填写的数字 d。
     • 上界 up = num_str[pos] if is_limit else 9。
     • 循环 d from 0 to up。
     • 剪枝: 如果 prev_digit == 4 且 d == 9，则跳过此次循环。
     • 递归: 累加 dfs 的结果。
       res += dfs(pos + 1, d, is_limit and (d == up), is_leading_zero and (d == 0))
   • 存储: 在 is_limit 和 is_leading_zero 均为 false 时，将结果存入 dp 表。

C++ 实现

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

long long dp[20][10];
string num_str;

long long dfs(int pos, int prev_digit, bool is_limit, bool is_leading_zero) {
    // 递归出口
    if (pos == num_str.length()) {
        return 1;
    }

    // 记忆化
    if (!is_limit && !is_leading_zero && dp[pos][prev_digit] != -1) {
        return dp[pos][prev_digit];
    }

    long long res = 0;
    // 确定当前位的上界
    int up = is_limit ? (num_str[pos] - '0') : 9;

    // 枚举当前位可以填的数字 d
    for (int d = 0; d <= up; ++d) {
        // 剪枝：不能出现 49
        if (prev_digit == 4 && d == 9) {
            continue;
        }

        res += dfs(
            pos + 1,
            d,
            is_limit && (d == up),
            is_leading_zero && (d == 0)
        );
    }

    if (!is_limit && !is_leading_zero) {
        dp[pos][prev_digit] = res;
    }

    return res;
}

long long solve(long long n) {
    if (n < 0) return 0;
    num_str = to_string(n);
    for (int i = 0; i < 20; ++i) {
        for (int j = 0; j < 10; ++j) {
            dp[i][j] = -1;
        }
    }
    // 初始 prev_digit 可以是任意不为4的数
    return dfs(0, -1, true, true);
}

int main() {
    long long L = 1, R = 100;
    // solve(X) 计算 [0, X] 满足条件的个数
    // 0 是一个满足条件的数，但题目通常问正整数区间
    // solve(R) 包含了 [0,R] 的所有数，包括 0
    // solve(L-1) 包含了 [0,L-1] 的所有数，包括 0
    // 相减后 0 的贡献被抵消，结果是 [L,R] 区间的个数
    long long ans = solve(R) - solve(L - 1);
    cout << "在 [" << L << ", " << R << "] 区间内不含 49 的数有: " << ans << endl; // 输出: 99
    return 0;
}

复杂度分析

• 时间复杂度: 状态数 * 转移复杂度。状态数约为 len * 10 (pos * prev_digit)。每次转移循环最多10次。所以大致是 O(len(X) * 10 * 10)，其中 len(X) 是数字 X 的位数，即 log10(X)。
• 空间复杂度: O(len(X) * 10)，用于 dp 表（记忆化）。d