一、题目

剑指 Offer 62. 圆圈中最后剩下的数字（约瑟夫环、DP、递归）

题目描述

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

示例1：

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

示例2：

1
2
输入: n = 10, m = 17
输出: 2

二、分析

这是一道典型的约瑟夫环问题。n个数字，每次删除第m个数字，求最后剩下的一个数字是多少。

我们用动态规划的思想去做这道题。首先假设 f(n,m)表示剩下的数字（可理解为最后一次删除后，剩下的数）。动态规划的思想就是要找f(n,m)和f(n-1,m)之间的关系，称为状态转换式。

先看f(n,m)中有n个数字，要每次删除m个数字。我们将其一步一步分解，看分解的子过程中有没有可以调用自身函数的小过程（递归思想）。

  • f(n,m)：我们先第一次删除第m个数字即(m-1)后，下一次删除的起始元素是m（序列如下）。由于m可能大于n，所以起始元素表示为m%n。

    0 1 2 3 4 5 … m-2 m-1（删除） m(下一次起点) m+1 … n-2 n-1

  • 之后在n-1个数字序列中，起始元素为m%n，再不断删除m个数字(序列如下)

    m(下一次起点) m+1 … n-2 n-1 0 1 2 3 4 5 … m-2 （序列1）

    发现此处有符合递归的性质。为了找出递推式，我们将找其和f(n-1,m)的关系。

  • 我们先分析f(n-1,m):表示有n-1个数字，起始元素为0，再不断删除m个数字(序列如下)

    0 1 2 3 4 5 … m-2 m-1（删除） m m+1 … n-2（序列2）

  • 由序列1和序列2映射关系可知，序列2加上m%n就对应到序列1
    $$
    f(n-1,m)+（m % n）=序列1的功能
    $$
    要保证映射转换过程一直在[0,n-1]范围内，所以要取余n，因此状态转换表达式为
    $$
    f(n,m)=(f(n-1,m)+(m % n) )% n=(f(n-1,m)+m )% n
    $$
    初始条件为:
    $$
    f(1,m)=0
    $$

三、代码

方法 迭代、递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*
* 题目：剑指 Offer 62. 圆圈中最后剩下的数字
* 描述：0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
* 实现:dp动态规划  
*         f(n,m) = [ (m % n) + f(n-1 , m) ] % n =( f(n-1, m) + m)%n 
         初始条件：f(n,1) = n-1

* 复杂度：递归：时间O(N)：递归需要执行N次
*			  空间 O(N)：递归栈空间消耗N的辅助空间

*        迭代：时间O(N)：循环消耗线性辅助空间
*			  空间 O(1)：常量辅助空间
*/

//递归写法
int lastRemaining(int n, int m) {
	if (n == 1) return 0;
	else return (m+lastRemaining(n-1, m)) % n;
}

//迭代写法
int lastRemainingA(int n, int m) {
	int dp1 = 0,dp2;
	for (int i = 2; i <= n; i++)
	{
		dp2 = ((dp1 + m) % i);
		dp1 = dp2;
		//可以将上面两句合并为：dp1=((dp1 + m) % i)
	}

	return dp1;
}

四、总结

DP动态规划要划分为小的子问题。递归式找到就很容易，麻烦就在找递推式。

此题中映射转换那里比较难理解。