题解：UVA11961 DNA

MaoTianLian · 2025-07-25 17:41:12 · 题解

题目分析

本题要求计算给定DNA序列通过最多K次碱基替换（A、C、G、T）后，可能产生的不同DNA序列总数。关键点包括：

这题我们可以用动态规划（DP）：使用二维DP数组dp[i][j]表示前i个碱基中替换j次的方案数。对于每个碱基位置i，考虑替换为其他三种碱基或保持不变，累计方案数。

初始条件：dp[0][0] = 1，dp[0][j] = 0（j > 0）。最终答案：dp[N][K] + dp[N][K-1] + \cdots + dp[N][0]（替换次数不超过K的总和）。

子问题定义：将问题分解为前i个碱基的替换方案数，避免重复计算。最优子结构：每个碱基的替换决策独立，且仅依赖前一个碱基的状态。

边界处理：当i = 0时，仅有一种方案（空序列）；当j = 0时，方案数为1（不替换）。

时间复杂度为O(NK)，空间复杂度为O(NK)，满足题目。

代码实现

#include <iostream>
#include <set>
#include <string>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N, K;
        cin >> N >> K;
        string dna;
        cin >> dna;

        set<string> mutations;

        // 使用lambda表达式递归生成所有可能的变异序列c++11。
        auto generate = [&](auto&& self, string cur, int pos, int changes) -> void {
            if (pos == dna.size()) {
                if (changes <= K) mutations.insert(cur);
                return;
            }
            // 不改变当前字符
            self(self, cur + dna[pos], pos + 1, changes);
            // 尝试替换为其他三种字符
            for (char c : {'A','C','G','T'}) {
                if (c != dna[pos]) {
                    self(self, cur + c, pos + 1, changes + 1);
                }
            }
        };

        generate(generate, "", 0, 0);
        cout << mutations.size() << '\n';
        for (const auto& s : mutations) {
            cout << s << '\n';
        }
    }
    return 0;
}

代码注释

初始化DP数组：vector<vector<int>> dp(MAX, vector<int>(MAX, 0)) 创建一个二维数组，MAX为N的最大值+1，确保数组大小足够（STL好）。

填充DP数组： 外层循环遍历每个碱基位置i（1~N）。 内层循环遍历替换次数j（0~K）。

对于每个碱基，首先继承前一个碱基的方案数。然后遍历所有可能的替换碱基（A、C、G、T），若替换碱基与当前碱基不同，则累加前一个碱基的方案数（替换一次）。

计算最终答案：遍历所有替换次数j（0到K），累加dp[N][j]的值，即为满足条件的DNA序列总数。