一、介绍约瑟夫环Josephus Problem是一个著名的数学和计算机科学问题大致意思是N个人围成一圈从第一个人开始报数报到第M个人就将其淘汰出圈然后从下一个人重新开始报数如此循环直到剩下最后一个人。求这个幸存者的初始位置。题目链接孩子们的游戏(圆圈中最后剩下的数)二、解决方案1. 模拟该方法是最直观的就是开辟一个数组记录哪些人被淘汰一直遍历下去直至只剩下一个人。class Solution { public: int LastRemaining_Solution(int n, int m) { vectorbool check(n, true); int cnt 0, idx 0, alive n; while(alive 1) { if(check[idx]) { cnt; if(cnt m) { cnt 0; alive--; check[idx] false; } } if(idx n) idx 0; } for(int i 0; i n; i) if(check[i]) return i; return -1; } };2. 递归上述的方法确实可以解决问题但是时间复杂度会有点高下面介绍一下很巧妙的方法。它的核心是假设一共有 n 个人在淘汰了一个之后就只剩下了 n - 1 个人那么我们是不是可以将 n - 1 个人看作一个新的约瑟夫环问题。这个思想就是递归的核心上面我们在了解了思想后来想几个关键问题。当人数从 n 变成 n - 1 的时候下一次淘汰人需要从这一次淘汰人的后一位开始计数这时会发现好像下一个人的编号不一定是从 0 开始的呀所以这里需要做一下映射。我们假设 k 是这一次淘汰的编号k (m - 1) % n那么下一次开始的位置就是 k 1它对应的新编号是 0、以此类推 k 2 - 1、k 3 - 2...。具体可以看下面 n5, m3 的例子黑色那一圈是初始 n 人旧编号淘汰下标 k 之后蓝色是剩下 n−1 人的新编号。所以可以推出旧编号 新编号 k 1但这对吗很明显在上图中 k3 已经超过原来的范围了所以实际是出旧编号 (新编号 k 1) % n。这样看是不是就成了比原来更小一层的问题了。这里可以将k (m - 1) % n公式合并到那个公式中可以得到旧编号 (新编号 m) % n。想一个边界情况如果 n 等于 1 呢这时其实就可以直接返回因为只有一个人而幸存者编号就是 0。所以递推公式如下 f(x)表示人数为 x 时幸存者的编号递归实现class Solution { public: int LastRemaining_Solution(int n, int m) { if(n 1) return 0; return (LastRemaining_Solution(n - 1, m) m) % n; } };dp实现class Solution { public: int LastRemaining_Solution(int n, int m) { vectorint dp(n 1); for(int i 2; i n; i) dp[i] (dp[i - 1] m) % i; return dp[n]; } };