求满足前缀0数≥k倍1数的n位字符串高效计数算法或公式

架构老林

2026-5-14

高效计算满足前缀约束的n位0-1字符串数量

嘿，我来帮你搞定这个计数问题！首先咱们明确下需求：要统计n位0-1字符串的数量，核心约束是字符串的每一个前缀里，0的数量至少是1的数量的k倍。你给的两个例子很直观：

n=5、k=3时，只有3个合法字符串：00000、00001、00010，所有前缀都满足0的数量≥3倍1的数量；
n=6、k=2时，有8个合法字符串，比如000011这类，每个前缀都符合要求。

你现有的递归解法逻辑是对的，但当n到1000时，递归的重复计算和栈深度问题会让它彻底跑不动，咱们来换更高效的方案。

现有递归的问题分析

你写的递归代码思路没问题，但有两个致命缺陷：

重复计算爆炸：不同的递归路径会反复计算同一个(c0, c1)状态，时间复杂度是指数级的，n=20可能就慢得明显了；
栈溢出风险：n=1000时，递归深度直接到1000，远超程序默认的栈容量，直接崩溃。

原递归代码贴在这里方便参考：

#include <iostream>
using namespace std;
int count;
int k;
// c0 is no. of 0s and c1 is no. of 1s
void rec(int c0, int c1, int n) {
    if(n>=0) {
        if(!n) {
            count++;
        }
        rec(c0+1,c1,n-1);
        if((c1+1)*k<=c0) {
            rec(c0,c1+1,n-1);
        }
    }
}
int main() {
    int n;
    cin>>n>>k;
    rec(k,0,n-k);
    cout<<count;
    return 0;
}

最优解法：动态规划（DP）

咱们用二维动态规划来消除重复计算，状态定义很清晰：

dp[i][j]：表示用了i个0和j个1，且所有前缀都满足约束的字符串数量。

状态转移逻辑

添加0：如果当前已经用了i个0和j个1，只要还没到n位，就能加一个0，所以dp[i+1][j] += dp[i][j]；
添加1：加1之后，1的数量变成j+1，必须满足当前0的数量i ≥ k*(j+1)（保证新的前缀符合约束），才能加1，所以dp[i][j+1] += dp[i][j]。

初始化

初始状态是dp[k][0] = 1：对应递归里的起点，先放k个0，这样后续才有可能加1（如果满足条件的话）；
其他不满足i ≥k*j的状态，dp[i][j]初始为0，因为本身就不符合约束。

最终结果

把所有满足i+j =n且i ≥k*j的dp[i][j]加起来，就是答案。

代码实现（C++）

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

int main() {
    int n, k;
    cin >> n >> k;
    // 用long long防止溢出，n=1000时数值可能很大
    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
    
    // 初始状态：k个0，0个1
    if (k <= n) {
        dp[k][0] = 1;
    }
    
    // 遍历已使用的字符总数，从k开始（初始状态用了k个字符）到n-1
    for (int total = k; total < n; ++total) {
        // 遍历0的数量，i的范围是：至少满足i >=k*(total-i) → i >= k*total/(k+1)，同时i<=total
        for (int i = max((k * total) / (k + 1), 0); i <= total; ++i) {
            int j = total - i;
            if (dp[i][j] == 0) continue;
            
            // 添加0，只要0的数量不超过n
            if (i + 1 <= n) {
                dp[i + 1][j] += dp[i][j];
            }
            
            // 添加1，需要满足i >=k*(j+1)，且1的数量不超过n
            if (j + 1 <= n && i >= k * (j + 1)) {
                dp[i][j + 1] += dp[i][j];
            }
        }
    }
    
    long long ans = 0;
    // 统计所有i+j=n且i>=k*j的情况
    for (int j = 0; j <= n; ++j) {
        int i = n - j;
        if (i >= 0 && i >= k * j) {
            ans += dp[i][j];
        }
    }
    
    cout << ans << endl;
    return 0;
}

这个DP的时间复杂度是O(n²)，空间复杂度O(n²)，对于n=1000来说，1001×1001的数组完全没问题，计算速度非常快。

空间优化：一维DP

如果想进一步节省空间，可以把二维数组压缩成一维，因为每个状态只依赖于左边（加0）和上边（加1）的状态。这里用逆序遍历避免覆盖未使用的状态：

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> dp(n + 1, 0);
    
    // 初始状态：0个1，k个0
    if (k <= n) {
        dp[0] = 1;
    }
    
    // 遍历已使用的字符总数
    for (int total = k; total < n; ++total) {
        // 逆序遍历1的数量，避免覆盖还未处理的状态
        for (int j = total / (k + 1); j >= 0; --j) {
            if (dp[j] == 0) continue;
            
            // 添加1：满足i = total -j >=k*(j+1)
            if (total - j >= k * (j + 1) && j + 1 <= n) {
                dp[j + 1] += dp[j];
            }
            // 添加0：用临时数组避免状态覆盖
            vector<long long> next_dp = dp;
            next_dp[j] += dp[j];
            dp = move(next_dp);
        }
    }
    
    long long ans = 0;
    for (int j = 0; j <= n; ++j) {
        int i = n - j;
        if (i >= k * j && i >= 0) {
            ans += dp[j];
        }
    }
    
    cout << ans << endl;
    return 0;
}

这个版本把空间复杂度降到了O(n)，对于内存紧张的场景更友好。

组合数学思路：反射原理的扩展

这个问题本质是带约束的格路计数：把字符串看作从(0,0)到(n0,n1)的路径，每一步向右（加0）或向上（加1），要求所有路径点(x,y)满足x≥k*y。

用反射原理可以推导公式，类似于卡特兰数的推导。对于每个合法的1的数量n1（满足n0 =n-n1 ≥k*n1 → n1 ≤n/(k+1)），合法路径数为：
$$
\sum_{n1=0}^{\lfloor n/(k+1) \rfloor} \left( \binom{n}{n1} - \binom{n}{n1 - 1} \right)
$$
当k=1时，这个公式就是卡特兰数的表达式，验证了正确性。不过计算大组合数需要高精度支持，如果题目要求精确值，需要用大整数库或者数组模拟；如果只需要模某个数，预处理组合数会更高效。

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

求满足前缀0数≥k倍1数的n位字符串高效计数算法或公式

现有递归的问题分析 #

最优解法：动态规划（DP） #