斐波那契字符串中字符B的计数优化及超时问题求助

字符串序列按以下规则生成：

• F[0] = "A"
• F[1] = "B"
• 当n > 1时，F[n] = F[n-1] + F[n-2]（拼接前两个字符串）

给定两个正整数n和k，需要统计字符串F[n]的前k个位置中字符'B'的数量。

我写了下面的解法，但运行时出现了超时错误：

public class Solution {
    public static long[] F = new long[50];
    public static Scanner input = new Scanner(System.in);

    public static long count(int n, long k) {
        if (n == 0 || k == 0) return 0;
        else if (n == 1) return 1;
        else {
            if (k > F[n - 1]) return count(n - 1, F[n - 1]) + count(n - 2, k - F[n - 1]);
            else return count(n - 1, k);
        }
    }

    public static void main(String[] args) {
        F[0] = 1; F[1] = 1;
        for (int i = 2; i < 46; i++) F[i] = F[i - 2] + F[i - 1];
        int T = input.nextInt();
        while (T-- > 0) {
            int n = input.nextInt();
            long k = input.nextLong();
            System.out.println(count(n, k));
        }
    }
}

我估计这个解法的时间复杂度是O(n²)，有没有办法优化它的时间复杂度？

测试用例 #

优化方案 #

你的解法超时的核心问题是重复计算：每次遇到k > F[n-1]时，都会递归调用count(n-1, F[n-1])来获取F[n-1]中'B'的总数，但这个值其实是固定的，完全可以提前预处理好，不用每次重复计算。

优化思路 #

1. 预处理两个数组：

   • len数组：存储每个F[n]的长度，本质就是斐波那契数列，len[0]=1，len[1]=1，len[n] = len[n-1] + len[n-2]
   • cnt数组：存储每个F[n]中'B'的总数，cnt[0]=0（F[0]是"A"），cnt[1]=1（F[1]是"B"），cnt[n] = cnt[n-1] + cnt[n-2]（因为F[n]是F[n-1]和F[n-2]拼接，B的总数是两者之和）

2. 修改递归逻辑：
   当k > len[n-1]时，直接用预处理好的cnt[n-1]代替count(n-1, len[n-1])，避免重复递归计算；同时处理k超过F[n]总长度的边界情况，直接返回cnt[n]。

优化后的代码 #

import java.util.Scanner;

public class Solution {
    public static long[] len = new long[50];
    public static long[] cnt = new long[50];
    public static Scanner input = new Scanner(System.in);

    public static long count(int n, long k) {
        if (n == 0 || k == 0) return 0;
        if (n == 1) return Math.min(k, 1); // 处理k可能大于1的情况（F[1]长度仅为1）
        if (k > len[n-1]) {
            return cnt[n-1] + count(n-2, k - len[n-1]);
        } else {
            return count(n-1, k);
        }
    }

    public static void main(String[] args) {
        // 预处理长度和B的总数
        len[0] = 1;
        len[1] = 1;
        cnt[0] = 0;
        cnt[1] = 1;
        for (int i = 2; i < 50; i++) {
            len[i] = len[i-1] + len[i-2];
            cnt[i] = cnt[i-1] + cnt[i-2];
        }
        int T = input.nextInt();
        while (T-- > 0) {
            int n = input.nextInt();
            long k = input.nextLong();
            // 边界处理：k超过F[n]总长度时直接返回全部B的数量
            if (k >= len[n]) {
                System.out.println(cnt[n]);
            } else {
                System.out.println(count(n, k));
            }
        }
    }
}

时间复杂度分析 #

• 预处理阶段：O(n)，n最大取50，耗时可以忽略。
• 每次查询：递归深度是O(n)，但没有重复计算，每个查询的时间是O(n)，由于n最大是50，即使有大量测试用例，也完全不会超时。

内容的提问来源于stack exchange，提问作者Hoàng Lộc