阿里算法工程师编程小测试-取石子游戏

问题描述

现在有一堆石子，共有N个。两个人轮流取石子，先拿完的人获胜。规定第一次不能拿N个，并且每一次拿的石子数量介于1和上一次拿的数量之间。现在的问题是，如果你作为先手，对于给定的N个石子，在保证能获胜的情况下，你最多能拿多少个？如果先手不能获胜，输出0即可。

问题分析

这个题有意思的地方就在于每次取石子时的数量限制。首先，我们可以肯定，你想赢得话，每次拿的石子数量肯定不能超过$N/2$，如果是这样子的话，下一次对手就可以直接把剩下的石子一次拿完，你就失败了。那么对于给定的石子数量，我最多能拿多少呢？

首先我们先来分析一下子问题。因为这个问题里面设计到的变量有当前剩余的石子数量$n$以及每次最多能拿的石子数量$k$，通过一番思考，我们会想到把子问题定义成如下的形式。

当有$n$个石子并且最多能拿$k$个石子的情况下，我能赢么？
能赢的话，最大拿几个（保证赢的情况下）？我将该问题记为$A(n,k)$

但是这个是子问题么？事实上，这个问题显然不是子问题，因为它没有考虑先后手的问题。换句话说，一开始的时候，问题可以写为$A(N,N-1)$，当你在这一步拿了$x$个石子后，你接下来要面对的问题不是$A(N-x,x)$，因为现在你已经不是先手了，而是对手先拿，所以问题的属性已经不一样了。

最优的动态规划算法

递推公式

就像在问题分析里面提出的问题一样，如果我们将子问题仅仅定义成$A(n,k)$是不行的。为了将先后手考虑进来，我们在额外定义一个符号$B(n,k)$代表在有n个石子并且我是后手的情况下，能否赢？因此，当你在第一步拿了$x$个石子后，你接下来要面对的问题就是$B(N-x,x)$，如果$B(N-x,x)$为真，那么$A(N,N-1)$就为真，也就是说我能够获得胜利。为了能得到我在第一步能拿的最大石子数量$x$，我们可以将x从$i = N/2$到$1$进行遍历，如果$B(N-x,x)$为真了，那么我可以赢，并且能多能拿的石子数量就是$i$ 。

这里的分析告诉我们如何去计算$A(n,k)$是真还是假。也就是说，
$$
A(n,k) = \sum_{i=1}^{k} {B(n-i,i)} > 0
$$
在上面的公式中，由于我们是先手，只要存在某个$i$，使得$B(n-i,i) =1$ 那么 $A(n,k)$也会为真。值得一提的是，在编程中，我们会将$i$从大到小遍历，如果$B(n-i,i) =1$了，就可以直接将$A(n,k)$设为真并退出。此外，还有三点需要注意一下。第一，当$k$大于$n$的时候,$A(n,k)$一定是真。第二，由于$n-i$可能小于0，在程序中需要做相应的处理。第三，我们不需要记录我能赢的时候，最多能拿多少个石子，这个信息可以通过回溯算法得到。

知道了如何计算$A(n,k)$之后，接下来的问题是如何计算$B(n,k)$了。根据上面的思路，我们可以马上得出$B(n,k)$的计算公式，即
$$
B(n,k) = \sum_{i=1}^{k} {A(n-i,i)} > 0
$$
但如果真的是这样的话，这样做就太复杂了。事实上，$B(n,k) = ！A(n,k)$，也就是说，这两者是相反的关系。这个从感觉上是很好理解的，不过这个如何从公式上来理解呢，这个就和初始化有关系了。

动态规划的初始化

对于该动态规划算法来说，他有两个二维表$A_{N \times N}$以及$B_{N \times N}$，计算每一个$B(n,k)$或者$A(n,k)$的时候要用的数据都是前面几行已经算出来的数据。因此我们可以按照行的顺序计算动态规划表格的每一个Cell即可。

因此，为了初始化该动态规划算法，我们只需要初始化二维表$A_{N \times N}$以及$B_{N \times N}$的第一行即可，也就是二维表$A(1,k)$以及$B(1,k)$，其中$k=[1,N-1]$。由于只有一个石子，并且$k \ge 1$，所以所有的$A(1,k)$都有真，所以的$B(1,k)$都为假。

这回导致在之后每一步的计算中$A(n-i,i)$和$B(n-i,i)$的值一定是相反的。所以，$B(n,k) = ！A(n,k)$。

算法实现

在下面的算法实现中，我把一维数组当二维数组用了。secondHand[(i-take)*(n+1) + take]就是表示secondHand[i-take,take]对应于公式中的$B(n-i,i)$，具体的代码如下。

#include <iostream>
#include <sstream>
#include <vector>
#include <math.h>

using namespace std;

int Find(int n)
{

    bool *firstHand = new bool[(n+1)*(n+1)];
    bool *secondHand = new bool[(n+1)*(n+1)];
    int firstTake = 0;

    for (int i = 1 ;i <= n;i++){
        firstHand[ 1*(n+1) + i ] = true;
    }
    for (int i = 1 ;i <= n;i++){
        secondHand[ 1*(n+1) + i ] = false;
    }

    for (int i = 2 ;i <= n;i++){
        for (int j = 1 ;j < n;j++){

            firstHand[i*(n+1) + j] = false;
            for(int take = j; take > 0 ; take --){
                if (secondHand[(i-take)*(n+1) + take] || take == i ){
                    firstHand[i*(n+1) + j] = true;
                    if (i==n && j==(n-1)){
                        firstTake = take;
                    }
                    break;
                }
            }
            secondHand[i*(n+1) + j] = !firstHand[i*(n+1) + j];

        }
    }

    delete[] firstHand;
    delete[] secondHand;
    return firstTake;
}

int main()
{
    int n = 13;
    cin>>n;
    cout << Find(n) << endl;
    return 0;
}

由于我们最终要获得的是$A(N,N-1)=1$是，我们最多能拿多少石子能保证赢，我在代码的29-31行记录了这个值，并将其返回了。

问题描述
问题分析
最优的动态规划算法
1. 递推公式
2. 动态规划的初始化
算法实现