一、题目

A、B两个人玩抢7游戏，游戏规则为：

A先报一个起始数字 X（10 ≤ 起始数字 ≤ 10000），B报下一个数字 Y （X - Y < 3），A再报一个数字 Z（Y - Z < 3），以此类推，直到其中一个抢到7，抢到7即为胜者；

在B赢得比赛的情况下，一共有多少种组合？

二、输入

起始数字 M （10 ≤ M ≤ 10000）

三、输出

B能赢得比赛的组合次数

四、示例

1
2
3
4
输入
10
输出
1

说明：B只有一种赢的组合，A起始选择10，B接着选择9，A接着选择8，B接着选择7赢得胜利。

五、题解

  1. 本题是爬楼梯问题的一个变种。爬楼梯是从从下往上，每次跳1层或者2层，到第n层的选择次数。本题包括2个人比赛，从上往下跳，每次基于对方当前层数跳1层或者2层
  2. 每次选择不是基于最优选择的博弈思维，而是枚举所有可能组合数
  3. 动态规划问题一般和求最值联系在一起，本题和爬楼梯问题解法一样，把求组合数理解为最大可能的组合

5.1 Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package org.stone.study.algo.ex202412;

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

/**
 * 抢7问题：A、B两个人玩抢7游戏，游戏规则为：
 *
 * A先报一个起始数字 X（10 ≤ 起始数字 ≤ 10000），B报下一个数字 Y （X - Y < 3），A再报一个数字 Z（Y - Z < 3），以此类推，直到其中一个抢到7，抢到7即为胜者；
 *
 * 在B赢得比赛的情况下，一共有多少种组合？
 */
public class BeFirst7 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 10
        int m = sc.nextInt();
        BigInteger ans = getCount(m);
        // 1
        System.out.println(ans);
    }

    public static BigInteger getCount(int m) {
        // dpA[i]表示A到i的总的走法数
        BigInteger[] dpA = new BigInteger[m + 2];
        // dpB[i]表示B到i的总的走法数
        BigInteger[] dpB = new BigInteger[m + 2];
        Arrays.fill(dpA, BigInteger.ZERO);
        Arrays.fill(dpB, BigInteger.ZERO);
        // A到m的走法总数，A先走到m
        dpA[m] = BigInteger.ONE;
        for(int i = m - 1; i > 6; i--) {
            // B到i的走法数，基于A的走法数（跳1或者2步）
            dpB[i] = dpA[i + 1].add(dpA[i + 2]);
            dpA[i] = dpB[i + 1].add(dpB[i + 2]);
        }

        return dpB[7];
    }
}

5.2 Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# A 从m（m >= 10)开始，B到达7的走法总数。A和B每次往下走1或者2步
def getCount(m):
    dp_a = [0] * (m + 2)
    dp_b = [0] * (m + 2)
    dp_a[m] = 1
    for i in range(m - 1, 6, -1):
        dp_b[i] = dp_a[i + 1] + dp_a[i + 2]
        dp_a[i] = dp_b[i + 1] + dp_b[i + 2]
    return dp_b[7]


if __name__ == '__main__':
    m = int(input())
    res = getCount(m)
    print(res)