【剑指 offer】圆圈中最后剩下的数字。（约瑟夫问题）

1、题目描述

0, 1, …, n-1这n个数字(n>0)排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。

求出这个圆圈里剩下的最后一个数字。

样例

输入：n=5 , m=3
输出：3

2、问题描述：

3、问题关键：

• f[i] = (f[i - 1) + m) % i。i个人最后剩下的相对于i - 1个人剩下的关系。
• f[1] = 0;

4、C++代码：

class Solution {
public:
    int lastRemaining(int n, int m){
        if (n == 1) return 0;
        vector<int> f(n + 1);
        f[1] = 0;
        for (int i = 2; i <= n; i ++)
            f[i] = (f[i - 1] + m) % i;
        return f[n];
    }
};