java - 查找可能的组合数

Question

有两个字母“X”和“Y”。需要使用这两个字母组成一个长度为 N 的字符串。

N 应以“Y”开头且不会有两个或更多个连续的“X”时，可能有多少种组合？

考虑 N = 7:

我通过以下方式解决了这个问题:

我的解决方案:

[没有。以字母“Y”开头的组合数] -[No:包含两个连续 X(n-1 可能)的组合 + No:包含 3 个连续 X(n-1 可能)的组合+.....]

=Math.pow(2,N-1)-[(N-2)(N-1)/2];

问题出在我要减去的部分。我遗漏了字符串中包含两个连续“X”和总共 3 个 X 的元素。类似地连续 2 个，总共 4 个 X。 我想找到一个通用公式，用于查找在没有“R”或更多连续“X”的情况下可能出现的字符串。

请帮我找到解决方案。

Answer 1

对于 R = 1 , 类似于斐波那契数列。

F(0) = F(1) = 1
F(N) = F(N-1) + F(N-2)

Java 中的最佳解决方案。

static int func(int n) {
    if (n < 1) return 0;   // as you required, F(0) = 0
    int n1 = 1, n2 = 1;    // however, for F(2..) we must have F(0) = 1
    for (int i = 2; i <= n; i++) {
        int n0 = n1 + n2;
        n2 = n1;
        n1 = n0;
    }
    return n1;
}

推广 R 的解决方案作为连续'X'的数量允许使用字符，您只需对 R + 1 求和序列中的前一个元素。正如我们所见，对于 R = 1公式是F(N) = F(N-1) + F(N-2) ;现在 R = 2公式是F(N) = F(N-1) + F(N-2) + F(N-3) .

因此我们推导出一个函数，它接受任何 N和 R .

static int func(int n, int r) {
    if (n < 1) return 0;   // as you required, F(0) = 0
    if (n == 1 || r < 1) return 1;
    int[] a = new int[r + 1];
    a[r] = a[r-1] = 1;     // however, for F(2..) we must have F(0) = 1
    for (int i = 2; i <= n; i++) {
        int x = a[0];
        for (int j = 1; j <= r; j++) {
            x += a[j];
            a[j-1] = a[j];
        }
        a[r] = x;
    }
    return a[r];
}