题解 | 孩子们的游戏(圆圈中最后剩下的数)

class Solution 
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int LastRemaining_Solution(int n, int m) 
    {
        int f = 0;  // 当 n=1 时，结果为 0
        for(int i = 2; i <= n; i++)  // 从 n=2 开始递推到 n
            f = (f + m) % i;  // 递推公式：f(n) = (f(n-1) + m) % n
        return f;  // 返回最终结果
    }
};

推导过程:

当 n = 1 时:

圈中只有一个人, 编号为 0, 因此 f(1, m) = 0

当 n >= 2 时:

第一轮报数后, 编号为 (m - 1) % n 的人出列, 剩下 n - 1 个人.

从出列的下一个人 (编号为 m % n) 开始, 重新编号为 0, 1, 2, ..., n - 2

此时问题转化为 n -1 个人的子问题, 子问题的解为 f(n - 1, m)

将子问题的解映射回原问题的编号, 得到递归公式:

f(n, m) = (f(n - 1, m) + m) % n