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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    // 根据公式 x = (m + x) % i; 状态转移公式 f(n, m) = (f(n-1, m) + m) % n
    // n个数之后去掉第m个数，剩下n - 1个数，依然要继续去掉第m个数。由此，从(n,m)的问题变成了(n - 1,m)的子问题，其中若是(n - 1,m)的子问题返回的最后一个数是x，则(n,m)返回的结果就是(m+x)%n
    public int LastRemaining_Solution (int n, int m) {
        // write code here
        // 没有小朋友的情况
        if(n == 0 || m == 0){
            return -1;
        }
        // 当只有一个人时，这个人的编号为0
        int x = 0;
        // 从小到大，更新x
        for(int i = 2; i <= n; i++){
            x = (m + x) % i;
        }
        return x;
    }
}