LeetCode 约瑟夫环（动态规划）

面试题62. 圆圈中最后剩下的数字

题目描述
法一：链表模拟（超时）

直接模拟删除的过程，比如开始的时候是从0位置开始遍历，每隔m删除一个数，当我们在依次遍历m-1位置的同时，将它们依次移动到链表的末尾。当遍历到m位置的时候就不添加到链表末尾而是直接删除，重复此过程直到剩下最后一个数为止。

 	int lastRemaining(int n, int m) {
        list<int> li;
        for(int i = 0; i < n; i++)
            li.push_back(i);
        while(li.size() != 1)
        {
            int cnt = m;
            while(cnt--)
            {
                if(cnt != 0)
                    li.push_back(li.front());
                li.pop_front();
            }
        }
        return li.front();
    }

法二：动态规划（AC）

既然是动态归化那我们肯定需要定义状态、初始状态和状态转移

状态： 在这里我们设状态dp[i] 表示一共有i个数时最后剩下数的位置

初始状态： 当状态为dp[0]显然不管m为多少最后一个数的位置就是0

状态转移： 状态转移就是当状态为dp[i]时怎么过渡到dp[i+1]，这里根据状态的含义我们知道dp[i]表示的是一共有i个数时最后剩下数的位置，dp[i+1]表示的是一共有i+1个数时最后剩下数的位置，其实很容易就能看出这两个位置不就是刚好相差m吗，因此状态转移方程为 dp[i] = dp[i - 1] + m;

然后我们就可以愉快的写出下面的代码

    int lastRemaining(int n, int m) {
        int lastPos = 0;  // 记录上一次最后被删除数的位置
        for(int i = 2; i <= n; i++)
        {
            lastPos = (lastPos + m) % i;  // 由于lastPos可能会大于i所以这里需要取模
        }
        return lastPos;
    }