[剑指 Offer 62]圆圈中最后剩下的数字（约瑟夫环问题：动态规划）

[剑指 Offer 62]圆圈中最后剩下的数字（约瑟夫环问题：动态规划）

题目：

• 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

示例 2：

输入: n = 10, m = 17
输出: 2
1
2
3
4
5
6
7
8
9

思路：

约瑟夫环：动态规划，采用数学推导出转移方程

• 对于[n, m问题]，首轮删除环中第m个数字后，得到一个长度为 n - 1 的数字环。

• 由于有可能 m > n，因此删除的数字为 (m - 1) % n，删除后的数字环从下个数字(即m % n)开始，

• 设 t = m % n，可得"新数字环"在"旧数字环"中的对应下标为: 【 t，t+1，t+2，…，0，1，…，t-3，t- 2 】（t-1为被删除的数字）

• 旧环删除数字 nums[(m-1)%n] 后的新环的起始下标为 旧环中的 m % n = t

• 删除一轮后的数字环变为[n-1，m问题]，其数字下标对应关系如下:

	      新环下标(本环)    新环下标在旧环(上环)下标中对应的下标
			   0                      (t+0)%n
			   1                      (t+1)%n
			  ...                      ...
			  n-2                     (t+n-2)%n
1
2
3
4
5

• 所以新环中的下标 x 与在旧环中对应下标 X 的关系为 X = (t + x) % n
• 删除到最后的新环中只有一个元素，下标为0，可以通过下标递推关系 找出其在"最旧环"中的下标

 X = (t + x) % n   --->  f(X) = (t + f(X - 1)) % n         (f(X - 1)为旧环下标，f(X)为旧环在其"上一层"新环中对应的下标)
                   --->       = (m % n + f(X - 1)) % n
                   --->       = (m + f(X - 1)) % n         (m % n % n == m % n)
1
2
3

• 最终的环，只有一个元素，下标为 0
• 推导最终环的上一个环，有两个元素…
• 再到上一个环，有三个元素，直到推到最原始的 n 个元素的环

代码：

class Solution {
    public int lastRemaining(int n, int m) {
        int x = 0;
        for (int i = 2; i <= n; i++) {
            x = (x + m) % i;
        }
        return x;
    }
}
1
2
3
4
5
6
7
8
9