动态规划逆推「约瑟夫环」问题

题目链接-来源：力扣（LeetCode）

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：

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

思路：

我们手工模拟一次删除过程，希望能找到规律。
设 n = 5，m = 3，则（粗体为待删除的元素，由于是循环排列的源泉，所以将开头循环部分拼接到尾部方便查看）
第一次 [0,1,2,3,4][0,1,2,3,4]
第二次 [3,4,0,1][3,4,0,1]
第三次 [1,3,4][1,3,4]
第四次 [1,3][1,3]
最后 [3]
考虑到经过若干次删除后，一定只剩下某个元素，虽然我们不知道这个元素具体是多少（本题中是3），但我们一定能知道元素的下标（最后剩余的元素，由于数组只剩一个元素，下标一定为0）。
于是我们记 f(i) 为第 i 次删除后，最终元素所在的下标位置， f(0) 代表未经删除的初始状态，也就是我们要的答案。则必有 f(n - 1) = 0。解下来我们需要从 f(n - 1) 一步一步反推出 f(0)。
从模拟结果中可以看出，第四次（n - 2）删除前，数组长度为 2，我们要删除第 m 个元素（此例中 m = 3），则删除的元素下标为 (m - 1) % 2。最终元素位于此元素之后，即有 f(n - 2) = m % 2。
以此类推，有 f(n - 3) = (f(n - 2) + m) % 3…
即 f(n - i) = (f(n - i + 1) + m) % i
于是我们从 f(n - 1) = 0 出发，即可一步一步推得 f(0)的值。

时间复杂度：O(n)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int lastRemaining(int n, int m) {
        int size = 2;
        int p = 0;
        while (size <= n) {
            p = (p + m) % size;
            size++;
        }
        return p;
    }
}