求解带连续动作限制的石头剪刀布获胜路径数问题

问题描述 #

给定一场两人进行的N轮石头剪刀布游戏（每轮获胜得1分，平局得0分），已知玩家1的出招序列（R=石头，P=布，S=剪刀）。要求计算玩家2在不连续出相同动作的前提下，实现获胜（总得分高于玩家1）的路径数量，结果需对1000000007取模避免整数溢出。

示例 #

• 示例1：3轮游戏，玩家1出招序列为RRR，玩家2可行的获胜序列为PRP、PSP、RPR，答案为3。
• 示例2：2轮游戏，玩家1出招序列为RP，玩家2可行的获胜序列为PS、RS（PP因连续出相同动作被禁止），答案为2。

问题探讨 #

这个问题属于纯粹的排列组合问题，还是因「禁止连续出相同动作」的约束更偏向动态规划（DP）问题？（已知所有排列组合问题都可转化为DP问题，但并非所有DP问题都属于排列组合范畴）

注：该题目为过往面试题，限时30分钟，暴力枚举所有可能序列不可行。

无约束情况分析 #

如果没有「禁止连续出相同动作」的约束，问题会简单很多，获胜路径数可按以下方式计算：

N轮全胜：1种路径
N-1轮胜：N种路径（对应N-1次获胜+1次平局）
N-2轮胜：N*(N-1)种路径（对应N-2次获胜+2次平局） + N种路径（对应N-1次获胜+1次失败）
最终答案 = 1 + N + (N*(N-1)+N) + ...

当前困境 #

但加入「禁止连续出相同动作」的约束后，玩家1的出招序列会直接影响结果。例如当玩家1出招序列为PRR时，玩家2无法实现3轮全胜。目前无法确定不同获胜轮次对应的路径数计算方式。

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