动态规划解决约瑟夫环问题

题目： 约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号0，1，2，3…n-1分别表示）围坐在一张圆桌周围。从编号为0的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，求最后一个出列的人。

1.经典解法

可以用链表来模拟约瑟夫环，每次在链表中删除第m个节点，然后不断，直至链表中只剩下一个节点。最后一个这个节点就是我们要求的节点。 注意：当迭代器扫描到链表末尾时，将迭代器移至链表头。

int lastRemaining(unsigned int n, unsigned int m){
    if(n<1||m<1)
        return -1;

    list<int> numbers;          //单链表模拟约瑟夫环（Josephus Ring）
    for(int i=0;i<n;++i)
        numbers.push_back(i);
    list<int>::iterator cur=numbers.begin(); //从第一个节点开始报数
    while(numbers.size()!=1){                //循环迭代至约瑟夫环只剩最后一个元素
        for(int i=0;i<m-1;++i){              //迭代m-1次找到需要移出环的元素
            ++cur;
            if(cur==numbers.end())           //迭代器扫描到链表末尾时，将迭代器移至链表头
                cur=numbers.begin();
        }
        list<int>::iterator next=++cur;
        if(next==numbers.end())
            next=numbers.begin();
        --cur;
        numbers.erase(cur);
        cur=next;
    }
    return *cur;
}

分析：经典解法易于理解，实现简单。但是重复遍历降低效率，没删除一个元素需要m步移动，对n个元素，时间复杂度为O(mn)。

2.动态规划求解

动态规划重点是要确定状态和状态转移方程。状态就是确定问题的解的表达式，状态转移方程就是上一阶段问题的解推出当前阶段问题解的递推式。

针对约瑟夫环问题，n个元素的环可以定义为f(n,m)，m表示每次移动的步数。则状态就是f(n,m)。那么对于n-1个元素的环，其最后一个被移除的元素就是f(n-1,m)。当环中只有一个元素时，f(1,m)=0。那么这里的重点和难点就是找出f(n,m)和f(n-1,m)之间的关系。也就是状态转移方程。

那么看如下分析： （1）第一个被删除的数为 (m - 1) % n，设下标为k。 （2）假设第二轮的开始元素下标为k+1，那么这n - 1个数构成的约瑟夫环为k + 1, k + 2, k +3, …..,k - 3, k - 2，k-1。做一个简单的映射。 k+1 —> 0 k+2 —> 1 … n-1 —> n-k-2 0 —> n-k-1 … k-1 —>n-2 可见，映射关系为p(x)=（x-k-1）%n，那么其从右到左的映射关系是p−1(x)=(x+k+1)%np^{-1}(x)=(x+k+1)\%n。因为右边最后出列的元素下标是f(n-1,m)，映射到左边就是p−1(f(n−1,m))=(f(n−1,m)+k+1)%np^{-1}(f(n-1,m))=(f(n-1,m)+k+1)\%n，又因为k=(m-1)%n，代入上面式中得: p−1(f(n−1,m))=(f(n−1,m)+k+1)%n=(f(n−1,m)+m)%np^{-1}(f(n-1,m))=(f(n-1,m)+k+1)\%n=(f(n-1,m)+m)\%n，即：

f(n,m)={0(f(n−1,m)+m)%nn=1n>1

f(n,m)=\begin{cases} 0&\text{n=1}\\ (f(n-1,m)+m)\%n & \text{n>1}\end{cases}

有了状态转移方程，我们可以使用迭代或者递归来完成问题求解。建议迭代，以免对不同阶段的问题重复求解。

下面以迭代方式实现：

int lastRemainingDP(unsigned int n, unsigned int m){
    if(n<1||m<1)
        return -1;

    int last=0; //n=1,最后移出环的元素
    for(int i=2;i<=n;++i)
        last=(last+m)%i;
    return last;
}

参考文献

[1]剑指Offer.何海涛.电子工业出版社. [2]解题笔记（10）——约瑟夫环问题.