题目描述

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能赢得比赛的组合次数

用例

输入

10

输出

1

说明

Java

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

public class Main {
    public static void main(String[] args) {
        // 创建一个Scanner对象用于接收用户输入
        Scanner scanner = new Scanner(System.in);

        // 从用户输入中接收一个整数M，表示游戏的起始或初始条件
        int M = scanner.nextInt();

        // 初始化两个BigInteger数组dpA和dpB，分别用来存储玩家A和B在每个可能的游戏状态下赢得游戏的方式的数量
        // 数组大小为M+2，是因为在迭代过程中需要访问当前状态之后的两个状态，这样可以避免数组越界错误
        BigInteger[] dpA = new BigInteger[M + 2];
        BigInteger[] dpB = new BigInteger[M + 2];

        // 使用BigInteger.ZERO初始化数组
        for (int i = 0; i < M + 2; i++) {
            dpA[i] = BigInteger.ZERO;
            dpB[i] = BigInteger.ZERO;
        }

        // 初始化dpA[M]为1，表示当游戏处于初始状态M时，玩家A有一种方式赢得游戏
        dpA[M] = BigInteger.ONE;

        // 从M-1开始递减至6，逐个计算每个可能的游戏状态下，玩家B和A赢得游戏的方式的数量
        for (int i = M - 1; i > 6; i--) {
            // 计算玩家B在状态i下赢得游戏的方式的数量
            dpB[i] = dpA[i + 1].add(dpA[i + 2]);

            // 计算玩家A在状态i下赢得游戏的方式的数量
            dpA[i] = dpB[i + 1].add(dpB[i + 2]);
        }

        // 最后，打印出玩家B在游戏状态7下赢得游戏的方式的数量
        System.out.println(dpB[7]);
    }
}