题目:
https://leetcode-cn.com/problems/find-the-winner-of-the-circular-game/
定义状态函数f(n,k) 为编号从0开始n个人在第k次淘汰情况下的幸存者
很显然第一次淘汰编号k-1的人,下一次从编号k开始
而f(n-1,k)根据定义是在编号0开始,我们只需要对坐标进行映射即可
于是有递推公式
f(n,k)=(f(n-1,k)+k)%n
代码:
class Solution {
public:
int fun(int n,int k){
if(n==1) return 0;
return (fun(n-1,k)+k)%n;
}
int findTheWinner(int n, int k) {
return fun(n,k)+1;//定义编号从0开始 题目是从1开始
}
};
原文:https://www.cnblogs.com/OfflineBoy/p/14649736.html