约瑟夫环问题的动态规划解法

发表于

问题简介

n 个人标号 0, 1, ... n-1。逆时针站一圈，从 0 号开始，每一次从当前的人逆时针数 k 个，然后让这个人出局。问最后剩下的人是谁。

问题分析

假设原环形队列为：

[0, 1, 2, 3, ... n-2, n-1]

则从第0个人开始，数k个（包括那个开始数数的人）出局，那么出局者的标号就会是(k-1) mod n。

令t等于k mod n，则原队列的标号为的人t为下一次开始数数的人，令其为新队列头。

在排除了(k-1) mod n后剩下的队列，我们将其队伍头重新编号为0，则新队列为：

[0, 1, 2, 3, ... n-2]

其中新队列的编号和旧队列存在如下的对应关系

新编号 旧编号
0 t
1 (t + 1) mod n
2 (t + 2) mod n
… …
n-2 (t - 1) mod n

令一个长度为n的队列，最终留下来的人编号为f(n)，那么我们可以知道在这两个队列中，留下来的那个人是不会变的，而他在两个队列中的编号具有如下的对应关系。

f(n) = (f(n-1) + t) mod n

初始解：f(1) = 0，因为只有一个人的话剩下的人一定是他。

解决代码

1
2
3
4
5
6
7
8
9
public class Solution {
    public int IceBreakingGame(int num, int target) {
        // num指开始时的总人数，target相当于数k个
        if (num <= 1) { return 0; }
        else {
            return (IceBreakingGame(num - 1, target) + target) % num;
        }
    }
}