问题“斐波那契字符串前k个字符中'B'字符的数量”的记忆解决方案？

Question

所以我遇到了这个编码问题：

A 和 B 的斐波那契字符串构造如下：
F(0) = "A", F(1) = "B"
F(n) = F(n-1) + F(n-2) n > 1

给定一个整数 n 和 k，计算字符 'B' 在 n-th 斐波那契字符串中的出现次数。
约束条件：n<= 45, k <= length of F(n).

目前我正在尝试使用 Memoization 解决它，但该解决方案导致 RTE 和 8/10 正确的测试用例。我希望在我的方法中得到一些修正，如果可能的话，甚至更好，一个更优化的解决方案。提前谢谢大家，这是我目前使用 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) = 'B' + 'A' = "BA" , f(3) = "BA" + 'B' = "BAB" 等等。

Answer 1

你的观察是正确的，但你没有得出结果：因为你连接了前两个字符串，结果字符串中 B 的数量是前一个字符串中 B 数量的总和 - 即，它是第 n 个斐波那契数.

这是一个用 Python 计算第 n 个斐波纳奇数的迭代解决方案（抱歉，我不擅长 C++）：

def fibo(n):
    if n < 2:
        return 1
    prev = 0
    curr = 1
    for _ in range(2, n+1):
        prev, curr = curr, prev+curr
    return curr

fibo(50)
12586269025