九章演算法 | Microsoft 面試題：我能贏

來自專欄 九章演算法 - lintcode/leetcode題解

撰文 | JZ

專欄 | 九章演算法

題目描述

有兩個人玩一個遊戲，給定一個最大可取整數 maxChoosableInteger，兩個人輪流從1~maxChoosableInteger 中取一個數，取過的數不可再取，若其中一方取過以後，

所有取過的數加起來的和大於等於desiredTotal，那麼這個人獲勝。

現在給你maxChoosableInteger和desiredTotal，問先手是否必勝，假定遊戲雙方均採取最優策略。

你可以假定給出的 maxChoosableInteger不超過20,desiredTotal不超過300。

樣例

輸入:maxChoosableInteger = 10desiredTotal = 11輸出:false

樣例說明

無論先手怎麼取數，先手都會輸掉遊戲。先手可以取1到10中的任何一個。如果先手取1，那麼後手可以取2到10中的任何一個。後手如果取10，那麼就可以贏得遊戲，因為此時和為1+10=11=desiredTotal。假如先手取其他的數，那麼後手仍然能贏得遊戲，只要使和大於等於11即可。

解題思路

1.我們讀完題發現這題似乎是一題經典的博弈問題，但是有一個很重要的限制條件————每個數只能取一次。

有了這個條件，我們很容易就能想到所有的取數方案，最多有maxChoosableInteger! 種，即 1~maxChoosableInteger 的全排列。

但是一一枚舉這maxChoosableInteger!種方案明顯超過了能承受的時間複雜度。

2.經過對這maxChoosableInteger!種方案的思考，我們可以發現，

雖然方案有階乘的數量級，但是這麼多方案有很多的部分重複計算了，

類似前綴和的思想，我們計算1~n的前綴和，只要計算出1~n-1的前綴和再加上n即可，避免了多餘的計算。

這裡我們同樣可以把之前計算的結果保留下來以方便之後的計算，我們稱之為記憶化搜索，

和前綴和不同的是，這裡用的是自頂向下(類似於分治的把大問題拆分為小問題的求解方法)的求解方法。

3.在記憶化搜索中，使用了兩個條件判斷勝利，

一是當前剩下的desiredTotal(減去了取走的數)小於等於0，

二是對於剩下的還未取的數，已經搜索過且是必勝的狀態，

假如這個狀態沒有搜索過，就進行dfs判斷這個狀態，直到遇到判斷過的狀態或desiredTotal小於等於0。

其實本題也可以用自下而上的動態規劃實現，狀態表示和記憶化搜索相同。

4.對於記錄狀態的數組，

我們使用01向量表示，0代表這個數沒有使用過，1代表已經使用過。

把1~maxChoosableInteger的使用情況定義為一個只有0,1的向量，

比如maxChoosableInteger=3，他們的使用情況有8種，分別是000(沒有元素被使用),001,010,100,011,110,101,111(所有元素都被使用)。

再把這個向量轉化成十進位數作為下標。

5.設maxChoosableInteger為n，

參考代碼

面試官角度

本題運用了記憶化搜索的方法，

能用記憶化搜索解出的能獲得hire的評價，

如果能把狀態壓縮為一個十進位數，則能獲得strong hire的評價。

Lintcode相關題目

不同的二叉查找樹

交叉字元串

九章參考答案

九章演算法 - 幫助更多中國人找到好工作，矽谷頂尖IT企業工程師實時在線授課為你傳授面試技巧