問題描述

題目如下：

給定一個(gè)表示分?jǐn)?shù)的非負(fù)整數(shù)數(shù)組。 玩家 1 從數(shù)組任意一端拿取一個(gè)分?jǐn)?shù)，隨后玩家 2 繼續(xù)從剩余數(shù)組任意一端拿取分?jǐn)?shù)，然后玩家 1 拿，…… 。每次一個(gè)玩家只能拿取一個(gè)分?jǐn)?shù)，分?jǐn)?shù)被拿取之后不再可取。直到?jīng)]有剩余分?jǐn)?shù)可取時(shí)游戲結(jié)束。最終獲得分?jǐn)?shù)總和最多的玩家獲勝。
　給定一個(gè)表示分?jǐn)?shù)的數(shù)組，預(yù)測玩家1是否會(huì)成為贏家。你可以假設(shè)每個(gè)玩家的玩法都會(huì)使他的分?jǐn)?shù)最大化。
示例 1：
　輸入：[1, 5, 2]
　輸出：False
　解釋：一開始，玩家1可以從1和2中進(jìn)行選擇。如果他選擇2(或者1)，那么玩家2可以從1(或者2)和5中進(jìn)行選擇。如果玩家2選擇了5 ，那么玩家1則只剩下1(或者2)可選。所以，玩家1的最終分?jǐn)?shù)為1+2=3，而玩家2為5。因此，玩家1永遠(yuǎn)不會(huì)成為贏家，返回False 。
示例 2：
　輸入：[1, 5, 233, 7]
　輸出：True
　解釋：玩家1一開始選擇1。然后玩家2必須從5和7中進(jìn)行選擇。無論玩家2選擇了哪個(gè)，玩家1都可以選擇233。最終，玩家1(234 分)比玩家 2(12分)獲得更多的分?jǐn)?shù)，所以返回True，表示玩家1可以成為贏家。
提示：
　· 1 <= 給定的數(shù)組長度 <= 20.
　· 數(shù)組里所有分?jǐn)?shù)都為非負(fù)數(shù)且不會(huì)大于 10000000 。
　· 如果最終兩個(gè)玩家的分?jǐn)?shù)相等，那么玩家 1 仍為贏家。

這道題目我改了兩次思路，都是錯(cuò)誤的，現(xiàn)在把錯(cuò)誤的思路也記錄下來。

拿到題目首先想到的就是暴力遍歷所有的情況，玩家1能贏一次就算贏。以示例1為例，如果玩家1取走1，玩家2取走2，玩家1再取走5，這樣玩家1就能勝出。這種思路就是把玩家2當(dāng)成傻子，玩家1取走1后，玩家2只剩2和5可以選擇，玩家2在明明知道取走5可以贏的情況下取走2，顯然是不符合題目要求的。

于是改進(jìn)了一下方法，每一個(gè)玩家都能選擇數(shù)列頭部或尾部的數(shù)字，那么每次讓他都取兩者中較大的那個(gè)——這算是一種貪心策略。但這種方法在示例2出現(xiàn)問題，玩家1取走7，玩家2必然取走233，后面就不用看了，玩家2穩(wěn)贏。

在示例2中，玩家1第一步就必須為接下來的步驟進(jìn)行謀劃，玩家1一定不能上來就取走7，取走7就會(huì)把233暴露出來，玩家2必然會(huì)取走233并獲勝。

綜上，玩家1和玩家2都不能是傻子。顯然，玩家1和玩家2得分的總和是固定的，因此，玩家1得到的分?jǐn)?shù)越多，玩家2得到的分?jǐn)?shù)就越少。每一步玩家都在規(guī)劃如何讓自己得到最高分?jǐn)?shù)的同時(shí)，讓對方得到最少的分?jǐn)?shù)——這就是一個(gè)零和博弈問題。

如果我們用score表示玩家1得到的分?jǐn)?shù)減去玩家2減去的分?jǐn)?shù)，那么玩家1就要讓score盡可能大，玩家2就要讓score盡可能小。以示例2為例，如果將所有情況都通過二叉樹的形式表示出來，很容易得到下圖。

圖1

從葉子節(jié)點(diǎn)向上回溯，計(jì)算score的值。注意，玩家1會(huì)讓score盡可能大，玩家2會(huì)讓score盡可能?。O大極小算法）。

先計(jì)算葉子節(jié)點(diǎn)的score，葉子節(jié)點(diǎn)的情況是固定的。

圖2

向上一層回溯。這一步是玩家1取數(shù)，玩家1希望score越大越好，因此兩個(gè)子節(jié)點(diǎn)中取score更大的那個(gè)賦給父節(jié)點(diǎn)。

圖3

倒數(shù)第二層由玩家2取數(shù)，玩家2希望score更小。

圖4

最高的一層。計(jì)算出的score為222，score>0，說明玩家1可以獲勝。

圖5

觀察上面的過程，我們是如何求max層節(jié)點(diǎn)（即玩家1取數(shù)）的score值呢？score = max(取走頭部數(shù)字后其余數(shù)字的score + 頭部數(shù)字，取走尾部數(shù)字后其余數(shù)字的score + 尾部數(shù)字)。

求min層節(jié)點(diǎn)（即玩家2取數(shù)）的score，score = min(取走頭部數(shù)字后其余數(shù)字的score - 頭部數(shù)字，取走尾部數(shù)字后其余數(shù)字的score - 尾部數(shù)字)。

實(shí)際上，這個(gè)max和min的過程統(tǒng)一成max，每一層都計(jì)算score = max(頭部數(shù)字 - 取走頭部數(shù)字后其余數(shù)字的score，尾部數(shù)字 - 取走尾部數(shù)字后其余數(shù)字的score)。當(dāng)然這樣計(jì)算出來的score就不再表示玩家1得到的分?jǐn)?shù)減去玩家2得到的分?jǐn)?shù)了，但最終的結(jié)果和前面的方法是完全等價(jià)的。

用這樣的方法來回溯樹得到的結(jié)果如下。

圖6

根據(jù)這個(gè)過程編寫代碼。

#include <math.h>

class Solution {
public:
    int Score(vector<int>& nums, int begin, int end) {
        if (begin == end) 
            return nums[begin];
        else {
            int beginScore = nums[begin] - Score(nums, begin + 1, end);
            int endScore = nums[end] - Score(nums, begin, end - 1);
            return max(beginScore, endScore);
        }
    }

    bool PredictTheWinner(vector<int>& nums) {
        int len = nums.size();
        int score = Score(nums, 0, len - 1);
        return score >= 0;
    }
};

運(yùn)行結(jié)果如下。

接下來思考一下如何減小時(shí)間消耗。觀察圖1中我們構(gòu)建的樹，可以發(fā)現(xiàn)有一些節(jié)點(diǎn)是重復(fù)的。其實(shí)我們發(fā)現(xiàn)，得分情況score和剩余的數(shù)列是相關(guān)的，比如如果剩余的數(shù)列是{5, 233}，那么score就一定是228，這很好理解，因?yàn)槭Ｏ聓5, 233}時(shí)輪到玩家1取數(shù)，只要玩家1不犯傻，就一定先取走233，把5留給玩家2。但重復(fù)計(jì)算了兩次。如下圖。

圖7

因此我們使用動(dòng)態(tài)規(guī)劃算法，減少重復(fù)計(jì)算的次數(shù)。

動(dòng)態(tài)規(guī)劃問題的核心三個(gè)要點(diǎn)：

1. 確定dp數(shù)組的含義。我們看到每個(gè)節(jié)點(diǎn)都是數(shù)組中連續(xù)的子列，因此用dp[i][j]表示下標(biāo)從i到j(luò)的子列的score值，。參考圖5。
2. 找到初始狀態(tài)。當(dāng)i==j時(shí)，就表示葉子節(jié)點(diǎn)，此時(shí) 。
3. 確定轉(zhuǎn)移方程。時(shí)，。

代碼如下。

#include <math.h>

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int len = nums.size();
        int dp[len][len];
        for (int i = 0; i < len; i++)
            dp[i][i] = nums[i];
        for (int i = len - 2; i >= 0; i--)
            for (int j = i + 1; j < len; j++)
                dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
        return dp[0][len - 1] >= 0;
    }
};

結(jié)果如下。

空間上，這個(gè)算法還可以繼續(xù)優(yōu)化。還是以示例2為例，dp矩陣的變化如下。

這里的dp是一個(gè)二維矩陣，但完全可以被優(yōu)化成一個(gè)長度為len的一維矩陣，優(yōu)化后的迭代過程如下。

代碼如下

#include <math.h>

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int len = nums.size();
        int dp[len];
        for (int i = 0; i < len; i++)
            dp[i] = nums[i];
        for (int i = len - 2; i >= 0; i--) {
            for (int j = i + 1; j < len; j++) {
                dp[j] = max(nums[i] - dp[j], nums[j] - dp[j - 1]);
            }
        }
        return dp[len - 1] >= 0;
    }
};

運(yùn)行結(jié)果如下。

這是一道最簡單的最大最小原理的應(yīng)用，事實(shí)上，在下棋類問題(五子棋、象棋)中最大最小原理的應(yīng)用更加深入廣泛，并使用α-β剪枝來節(jié)約時(shí)間開銷，這里就不再贅述了。

這篇文章寫起來不易，如果它對你有幫助的話，麻煩給個(gè)贊吧！！