第n个斐波那契字符串前k个字符中'B'计数：DP方案及代码优化

斐波那契字符串由'A'和'B'构造，规则如下：

• F(0) = "A"，F(1) = "B"
• 当n>1时，F(n) = F(n-1) + F(n-2)（字符串拼接）

给定整数n和k，统计第n个斐波那契字符串的前k个字符中'B'的出现次数，约束条件为n≤45，k≤F(n)的长度。

我用记忆化方法实现时出现运行时错误（RTE），仅通过8/10的测试用例，需要纠正思路并得到更优的动态规划（DP）解决方案。以下是我的C++实现代码：

void solve(int n, long long k) {
    vector<string> fib;
    fib.push_back("A"); fib.push_back("B");
    if(n==0) {
        cout << 0 << endl;
    }
    else if (n==1 && k==1) {
        cout << 1 << endl;
    }
    else if (n==1 && k==0) {
        cout << 0 << endl;
    }
    else {
        string toPush = fib[1] + fib[0];

        while(toPush.length() < k) {
            fib.push_back(toPush);
            toPush = fib[fib.size()-1] + fib[fib.size()-2];
        }

        fib.push_back(toPush);

        long long countB = 0;
        string finalStr = fib[fib.size()-1];
        for(long long i = 0; i<k; i++) {
            if(finalStr[i]=='B') countB++;
        }
        cout << countB << endl;
    }
}

我的思路是基于拼接顺序F(n-1)+F(n-2)，比如F(2)="BA"，F(3)="BAB"等。

原代码的核心问题是直接存储拼接后的字符串：当n达到45时，F(45)的长度是1134903170，这是一个超过10亿的长度，直接存字符串会耗尽内存，导致运行时错误（RTE）。完全不需要生成完整字符串，只需要统计长度和B的数量即可。

我们可以预处理两个DP数组，再通过递归/迭代的方式计算结果：

1. 预处理数组：

   • len[i]：存储F(i)的长度，递推公式：len[0] = 1，len[1] = 1，len[i] = len[i-1] + len[i-2]（i≥2）
   • cntB[i]：存储F(i)中'B'的总数，递推公式：cntB[0] = 0，cntB[1] = 1，cntB[i] = cntB[i-1] + cntB[i-2]（i≥2）

2. 递归计算前k个字符的B数：

   • 如果n=0：返回0（F(0)是"A"，没有B）
   • 如果k ≤ len[n-1]：前k个字符全部来自F(n-1)，直接计算count(n-1, k)
   • 如果k > len[n-1]：前len[n-1]个字符的B数是cntB[n-1]，剩下的k - len[n-1]个字符来自F(n-2)的前部分，加上count(n-2, k - len[n-1])

C++实现代码 #

#include <iostream>
#include <vector>
using namespace std;

long long countB(int n, long long k, vector<long long>& len, vector<long long>& cntB) {
    if (n == 0) return 0;
    if (k == 0) return 0;
    if (k <= len[n-1]) {
        return countB(n-1, k, len, cntB);
    } else {
        return cntB[n-1] + countB(n-2, k - len[n-1], len, cntB);
    }
}

void solve(int n, long long k) {
    vector<long long> len(46);
    vector<long long> cntB(46);
    len[0] = 1;
    len[1] = 1;
    cntB[0] = 0;
    cntB[1] = 1;
    for (int i = 2; i <= n; ++i) {
        len[i] = len[i-1] + len[i-2];
        cntB[i] = cntB[i-1] + cntB[i-2];
    }
    cout << countB(n, k, len, cntB) << endl;
}

int main() {
    int n;
    long long k;
    cin >> n >> k;
    solve(n, k);
    return 0;
}

代码说明 #

• 用long long存储len和cntB，避免n=45时溢出
• 递归过程不需要生成任何字符串，只通过数组值和逻辑判断计算结果，内存占用极小
• 预处理数组的时间复杂度是O(n)，递归计算的时间复杂度是O(n)，整体效率极高

内容的提问来源于stack exchange，提问作者dvmbCateDoinAStroll