题目描述

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。

下一个人继续从 1 开始报数。

n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

解题思路

最容易想到的就是模拟法。用数组或者链表模拟每一个人，然后暴力计算。

不过这种方法容易出错，而且时间复杂度也比较高。

注意到题目中每一轮游戏结束后，下一轮游戏将从出局的后一个人开始报数。如果把这个人的编号移动到第一个人，那么不就相当于n - 1个人从头开始玩游戏吗？这里面显然存在某种联系。

找到这种联系，就可以使用动态规划。

动态规划

令dp[n] 表示n个人玩游戏（编号0到n-1）最后剩下的人，我们考虑dp[n]和dp[n + 1]的关系。

假设n+1个人玩游戏（编号0-n），令第一轮从编号k开始报数，第m个报数的人编号为n，编号为n的人离开。继续玩游戏，就变成了n个人从编号0开始报数，持续n-1轮游戏后，最后剩下的人编号显然就是dp[n]。

对于k，为了让第m个报数的人编号正好为n，则有 (k + m - 1) % (n + 1) = n，即(k + m) % (n + 1) = 0。

于是k = a(n + 1) - m。其中a为系数，使得k的取值范围为[0，n]。

第一轮从0开始报数，最后得到结果为dp[n + 1]；从k开始报数，结果为dp[n]。于是我们得到了状态转移方程

(dp[n + 1] + k) % (n + 1) = dp[n]，即(dp[n + 1] + a(n + 1) - m) % (n + 1) = dp[n]

转化一下，得到dp[n + 1] = (dp[n] + m) % (n + 1)。

通项公式 dp[i] = (dp[i - 1] + m) % i。

首项为dp[1] = 0。

c++代码

虽然是用的动态规划的思路，但实际后一项只和前一项有关，用不到dp数组，一个变量加一个循环就好了。

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @param m int整型
     * @return int整型
     */
    int ysf(int n, int m) {
        int ans = 0;
        for(int i = 2; i <= n; ++i) ans = (ans + m) % i;
        return ++ans;
    }
};