java - 重叠集的算法

Question

有一个游戏包含 N 轮。每轮结束后，获胜者(你或我)将获得一分。游戏结束时得分较多的玩家获胜。

你希望在游戏的每一轮之后你的分数至少是我的 M 倍。

For Example N=3 , M=1
the possible sequence of winners of rounds are:
DDD     // D is you and M is me
DMD
DDM

MDD    // Is not possible as you are having 1 point and i am having zero so condition violted 

我的方法:

在一个特定的游戏中，只有两种可能性是你赢或我赢，所以我进行递归调用来计算两种可能性的得分。

                                   D           
                                M           D          // At M+1 game(M wins or D wins)
                              D or M      D or M       // At M+2 game(M wins or D wins)
                    .
                    .
                    . ans so on
                                 At last round return 1

代码:

public static int score(int rounds, int m, int score1, int current, int score2) {
    int sum=0;

    if (current == rounds && score2 == 0) return 1;
    if (current == rounds && score1 / score2 >= m) return 1;
    if (score2 != 0 && score1 / score2 < m) return 0;
    if (score2 == 0 || score1 / score2 >= m) {
        sum += score(rounds, m, score1, current + 1, score2 + 1);
        sum += score(rounds, m, score1 + 1, current + 1, score2);
    }
    return sum;
}

System.out.println(score(rounds,m,m,m,0));

对于 10^6 范围内的较大 N 值，此解决方案需要很长时间。我怎样才能加快我的方法。

Answer 1

假设您要玩 N 场比赛(按顺序)，并且在每一步中您都记录玩家 A 获胜还是玩家 B 获胜。您生成了一个看起来像 AABABBAABA 等的序列。您想要计算这样的序列的数量，其中 A 的数量是 B 的 M 倍(我假设您的意思至少是 M 倍)。由于 N 是固定的，因此 B 的数量有一个上限。 IE。 #B's + #A's = N 和#A's >= M*#B's，所以 (M+1)*#B's <= N 所以#B's <= N/(M+1).

假设字符串中最多可以有 KB 个字符(总共有 N 个字符)。对于每个 1 <= k <= K，有 N 选择 k 种方式来放置 B(假设您有 k 个)，其余的是 A。那么，总共有SUM(k=0..K)(N选k)这样的可能性。

因此，与其使用代码生成所有这些，不如让您的代码计算(N 选择 k)个值并将它们相加。