PROBLEM

剑指 Offer 62. 圆圈中最后剩下的数字

难度 简单

MY ANSWER

无。

BETTER SOLUTION

约瑟夫环问题，使用动态规划解答。dp[n]表示n个数删除第m个的最终解，可由dp[n-1]得出，找出dp[n-1]与dp[n]删除一次第m个后的对应关系即可得出递推方程。

dp[n]删除一次后的序列：m, m+1, … , m-3, m-2

dp[n-1]的序列： 0, 1 , … , n-3, n-2

因此可得dp[n] = (dp[n-1] + m) % n

因为只需要上一步结果，因此使用一个变量存储上一步结果即可。

时间复杂度O(n)，空间复杂度O(1)。

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;
    }
};

SUMMARY

约瑟夫环问题使用动态规划，配合找对应规律。