您当前的位置：首页 > 经验交流

从30分到100分：一道C++动态规划题的重构全过程

时间：2026-02-20 09:27:01 来源：作者：

在算法竞赛和求职笔试中，动态规划（Dynamic Programming, DP）是必考的核心题型。然而，很多初学者常常陷入这样的困境：明明写出了DP代码，也能通过样例，但提交后却只有30分——要么答案错误，要么超时超内存。

本文将以一道经典DP题目为例，完整复盘我从30分低效实现到100分满分优化的重构全过程。你将看到：边界条件的疏漏如何导致答案偏差、状态转移的错误如何累积，以及空间优化技巧如何让代码起死回生。

一、初版代码：能跑通样例的30分实现

1.1 题目背景

我们选取一道典型DP题——"不同的子序列"（LeetCode 115）作为案例。题目要求：给定两个字符串 s 和 t，统计在 s 的子序列中，t 出现的个数。

1.2 第一版实现

拿到题目后，我快速写下了以下代码：

int numDistinct(string s, string t) {
    int m = s.size(), n = t.size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 || j == 0) {
                // 粗暴处理边界
                if (s[i] == t[j]) dp[i][j] = 1;
                continue;
            }
            
            if (s[i] == t[j]) {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[m-1][n-1];
}

1.3 30分的原因分析

本地测试样例通过后，我满怀信心地提交，结果只得了30分。问题出在哪里？

问题1：边界条件处理错误
在DP问题中，边界条件是决定成败的关键。当 t 为空字符串时，s 中应有且仅有1种子序列（即空串）与之匹配。但我的代码直接访问 dp[i][0]，当 n=0 时，第二层循环根本不执行，导致数组未被正确初始化。

问题2：数组维度设置不当
我的 dp 数组大小为 m × n，这导致两个严重隐患：

当 i=0 或 j=0 时，访问 dp[i-1][j-1] 会越界
无法自然表达空字符串边界，导致逻辑复杂且易错

问题3：未考虑整数溢出
题目要求结果对 10^9+7 取模，但我的代码完全没有处理。当数据量稍大时，整数溢出将导致答案错误。

二、第一次重构：修正核心逻辑（60分）

2.1 标准DP框架的建立

经过查阅资料，我意识到正确的DP实现应该遵循以下规范：

int numDistinct(string s, string t) {
    int m = s.size(), n = t.size();
    // 关键1：开 (m+1) × (n+1) 的数组，容纳空串边界
    vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, 0));
    
    // 关键2：正确初始化边界
    for (int i = 0; i <= m; i++) {
        dp[i][0] = 1;  // t为空串时，匹配数为1
    }
    // dp[0][j] 对于 j>0 保持为0（s为空串时无法匹配非空t）
    
    // 关键3：从1开始遍历，对应字符串的0索引
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i-1] == t[j-1]) {
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % 1000000007;
            } else {
                dp[i][j] = dp[i-1][j] % 1000000007;
            }
        }
    }
    return dp[m][n];
}

2.2 重构要点解析

维度调整：将数组大小设为 (m+1) × (n+1)，用第0行和第0列表示空串状态，这是DP题的标准技巧
边界初始化：dp[i][0] = 1 正确表达了"空串是任何字符串的子序列"这一事实
取模处理：在每次累加后取模，防止溢出

这次重构后，代码通过了所有基础测试用例，得分提升到60分。但问题仍未完全解决——当 s 和 t 长度达到1000时，内存消耗过大，运行时间也不理想。

三、第二次重构：空间优化大作战（80分）

3.1 分析空间瓶颈

观察状态转移方程可以发现：dp[i][j] 的计算只依赖当前行（dp[i-1][j]）和上一行（dp[i-1][j-1]）的数据。这意味着我们无需保留整个二维表！

3.2 滚动数组优化

采用滚动数组技巧，将空间复杂度从 O(m×n) 降至 O(n) ：

int numDistinct(string s, string t) {
    int m = s.size(), n = t.size();
    vector<long long> dp(n + 1, 0);
    dp[0] = 1;  // 空串的匹配数
    
    for (int i = 1; i <= m; i++) {
        int pre = dp[0];  // 保存左上角的值
        dp[0] = 1;        // 每行开始，空串匹配数仍为1
        
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];  // 保存当前值，作为下一轮的左上角
            if (s[i-1] == t[j-1]) {
                dp[j] = (pre + dp[j]) % 1000000007;
            } else {
                // dp[j] 保持不变（相当于继承上一行的值）
            }
            pre = temp;  // 更新左上角
        }
    }
    return dp[n];
}

3.3 优化要点

一维数组复用：dp[j] 在更新前存储的是上一行的 dp[i-1][j]
左上角保存：用 pre 变量保存 dp[i-1][j-1]，防止被覆盖
更新顺序：内层循环必须从左到右，因为 dp[j] 依赖左边的 dp[j-1]（已被更新为当前行）和 pre（保存的左上角）

优化后，内存使用大幅降低，运行时间也有所改善，得分提升到80分。但仍有10%的测试点超时——问题出在哪里？

四、第三次重构：常数优化与细节打磨（90分）

4.1 剪枝策略

观察发现：如果 t 的长度大于 s，那么匹配数必然为0，可以直接返回。

int numDistinct(string s, string t) {
    int m = s.size(), n = t.size();
    if (n > m) return 0;  // 剪枝
    
    // 后续代码不变...
}

4.2 数据类型优化

将 vector<long long> 改为 vector<unsigned int>，利用无符号整型的自动取模特性：

vector<unsigned int> dp(n + 1, 0);
// 模运算自动由溢出处理，但需确保 2 * MOD < UINT_MAX

4.3 循环顺序微调

将外层循环改为遍历较短的字符串（如果 t 比 s 短很多）：

// 让较短的字符串作为列，减少内存访问
if (n > m) return 0;
// 保证 n <= m，使 dp 数组尽可能小

经过这些常数优化，代码终于通过了所有时间测试，得分达到90分。

五、终极优化：从90分到100分的最后一公里

5.1 发现隐藏的重复计算

仔细分析后发现：在每一行的计算中，当 j > i 时，dp[j] 其实必然为0——因为短串无法匹配长串。我们可以利用这一性质缩小循环范围。

5.2 动态边界优化

int numDistinct(string s, string t) {
    int m = s.size(), n = t.size();
    if (n > m) return 0;
    
    vector<unsigned int> dp(n + 1, 0);
    dp[0] = 1;
    
    for (int i = 1; i <= m; i++) {
        int pre = dp[0];
        dp[0] = 1;
        
        // 关键优化：j 只需遍历到 min(i, n)
        int limit = min(i, n);
        for (int j = 1; j <= limit; j++) {
            int temp = dp[j];
            if (s[i-1] == t[j-1]) {
                dp[j] = (pre + dp[j]) % 1000000007;
            }
            // 不等时 dp[j] 保持不变
            pre = temp;
        }
        
        // 对于 j > i 的部分，dp[j] 保持为0，无需处理
    }
    return dp[n];
}