python约瑟夫环问题

# -*- encoding: utf-8 -*-
'''
@Time    :   2022/06/14 14:20:06
@Author  :   wangjie648 
@License :   (C)Copyright 2017-2018, Liugroup-NLPR-CASIA
@Desc    :   约瑟夫环,f(n, m)表示n个人序号m被删除后剩余的那个索引
'''
def lastRemaining(n: int, m: int) -> int:
    # 递归
    return 0 if n==1 else (lastRemaining(n-1, m)+m)%n

    # 原始dp
    dp = [0] * (n + 1)
    for i in range(2, n + 1):
        dp[i] = (dp[i - 1] + m) % i
    return dp[-1]

    # 空间压缩
    x = 0
    for i in range(2, n + 1):
        x = (x + m) % i
    return x

    n_list = list(range(1, n+1))
    while n > 1:
      for i in range(n):
        if i == (m-1)%n:
          n_list.pop(i)
          break
        else:
         nlist.append(nlist.pop(i))
      n = len(n_list)