解题思路
- 经典约瑟夫环
plus
经典记忆化搜索技巧 - \(f(n,m)=\begin{cases}0 & (n=0)\\ [f(n-1,m)+m]\%n&(n>0)\end{cases}\)
代码
class Solution {
public:
struct pair_hash {
inline size_t operator()(const pair<int,int>&p)const{
return (((unsigned)p.first<<17)+p.second);
}
};
unordered_map<pair<int,int>,int,pair_hash>josephus;
int lastRemaining(int n, int m) {
auto state=make_pair(n,m);
if(josephus[state])return josephus[state];
return josephus[state]=(n?(lastRemaining(n-1,m)+m)%n:1);
}
};