题目描述

解题思路

为什么不使用直接删除？

DP

https://leetcode.cn/leetbook/read/illustration-of-algorithm/oxp3er/

本题就是经典的约瑟夫环问题。

怎么推出递推公式呢？
例如在[n,m]问题中，首轮删除环中第 m 个数字后，得到一个长度为 n - 1 的数字环。由于有可能 m > n ，因此删除的数字为 (m−1)%n，那么删除后从m%n开始，此时设t=m%n，
此时的序列可以表示为 t，t+1，t+2，…，0，1，…，t-3，t-2，此时t-1已经被删除，把 t-1 后面的放到前面。
删除一轮后的数字环也变为一个「n-1, m问题」，观察以下数字编号对应关系：此时可以和[n-1,m]做一个对比，：

所以此时可以比较得出递推关系：x→(x+t)%n
换而言之，若已知「n-1, m问题」的解 f(n−1) ，则可通过以上公式计算得到「n, m 问题」的解 f(n) ，即：


dp含义：表示[i,m]问题的的解，也就是i的范围，删除后剩下的数字。
递推公式：见上
初始化：dp[1]删多少都只剩下0。
遍历顺序：从前向后

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