动态规划的第二大类问题——石子问题（上）

前言

大家好，今天我们来聊聊动态规划的第二大类问题——石子问题。

Stone Game 在 Leetcode 上有 7 题之多，但大多数的套路都是类似的。

本文将通过 Stone Game I 和  Stone Game III 这两道经典的博弈论相关的题目，再次探究动态规划的魅力，希望能帮助大家对博弈和 DP 都有更好的理解。

同时本文还会详细讲解Top Down 和 Bottom Up这两种 DP 解法。

那在看题目之前，我们稍微来回顾一下动态规划和博弈。

动态规划

• 它是一种算法上的优化
  
• 它是一种状态的压缩
  
• 它是使用cache， 用来避免重复的计算
  

博弈入门

博弈，主要是研究一种激励结构间的相互作用，预测游戏中的个体行为，研究它们的优化策略。

我们举个简单的例子：

假设小六和小七在玩猜拳，如果小六已经猜到了小七会出布，那么小六肯定会出剪刀，因为剪刀能使小六获胜。

但是，如果小七已经猜到小六会猜到自己出布，那么小七会不会改变策略呢？

如果小六又猜到了小七已经猜到了自己猜到了小七的想法 ，他又会怎么做呢？

从以上例子我们可以看出，两个人的猜在不停的进行博弈，在这过程中都希望选出一个对自己最有利（Optimal) 的方案。

那什么是最优 Optimal 的方案？

说的简单一点，就是当 player 面前有多种选择的时候，他会选择对自己最有利的那一个。

以以上的猜拳作为例子，对于小六来说，他有三种选择，那就是石头，剪子，和布。

对于每一种选择，可能都会引起小七不同的反应。

例如小六出布的话小七猜到的概率可能更高，这种情况，小六就应该出剪刀或者石头，因为这两个没这么容易被猜到，对于自己会更加有利。

💡小提示：一般博弈类的题目都会有 "Optimal" 这字眼哦！一看到这个词，我们就可以往这方面去想了。

对于博弈类的问题，一般有以下 3 种方法：

穷举、贪心、DP

穷举就是把所有的情况都列举出来，也是暴力里面的最暴力。

对于博弈类的问题，最简单的做法就是把所有的情况都列举出来然后选择最优的那个方案，但很多都是NP复杂度。

但是也有很多博弈问题有贪心的解法（拥有所谓的必胜策略）。

而我们的石子游戏系列就是一种可以使用状态压缩从而避免NP复杂度的题目 （下面会详细说到什么是状态压缩）。

博弈是一门博大精深的学问，我们并不会去深入探究。本文是试图通过简单的吧博弈（石子游戏）去更好的了解 DP。

Top Down & Bottom Up:

我们接下来还要了解一下什么是 DP 的 Top Down 和 Bottom Up ，以及他们的区别是什么。

对此，我们又请来了我们熟悉的朋友：斐波那契数列。

斐波那契数列的关系式 ： f(n)=f(n-1)+f(n-2)

1. 下面是我们使用递归的暴力代码
   

publicintf(intn) {

    if(n<=2){

     returnn;

     }

     returnf(n-2) +f(n-1);

}

我们如果把 n 打印一下的话，我们可以发现有很多个 n 被重复访问了。

因为 f(n) 的值是不变的，所以我们对于重复访问可以不去做重复的计算，而是把它的值在第一次访问完后给记录下来。

2. 从递归转换到 Top Down

classSolution {

 intdp[]=newint[100]; //假设 n 在100以内

 publicintf(intn) {

   if(n<=2){//base case

       returnn;

   }

   if(dp[n] !=0 ){//非第一次访问，值已被记录，可直接返回

       returndp[n];

   }

   dp[n] =f(n-2) +f(n-1); //第一次访问并记录f(n)的值

   returndp[n];

 }

}

我们可以看出 Top Down 跟递归是非常相似的，我们只是加多了去记录重复的这一步。我们从 f(n) 开始一层一层往下走，最终到达 f(1)，最后把最下面的值回传上来。

3. BottomUp

publicintclimbStairs(intn) {

 if(n<=2){

    returnn;

 }

 // 对basecase 的初始化

 intfirst=1;

 intsecond=2;

 for(inti=2; i<n; i++){

   inttemp=second;

   second=first+second;

   first=temp;

 }

 returnsecond;

}

Bottom Up 其实就是对关系式的表达。

我们的关系式是 f(n)=f(n-1)+f(n-2)。

但与 Top Down 不同的是我们需要先 initialize Base Case, 这里的 Base 就是 n=1 和 n=2 的时候，也就是我们的first和second。

然后我们根据 Base 一层一层的往上面建立，从 f(1) 建立到f(n)。

总结下 Top Down 和 Bottom Up 的区别：

• TopDown 和 Bottom Up 两个听起来好像不太好记，但其实不然。一个是从上到下，一个是从下到上，这里我们只要记住 Base Case 是下就行了。做 Top Down 的时候，Base Case 是最后被访问的，而 Bottom Up 则相反，我们会先 initialize Base Case。
  
• 从时间和空间复杂度来说两者都是差不多的，但是因为 Top Down 用的是递归，对于 Runtime Stack 的要求会比较大。
  
• Bottom Up 的关系都能从 Top Down 的递归那里看出来，第一眼看不出关系式的话，建议先从 Top Down 入手。
  

下面进入今天的主题，石子游戏。

Stone Game I

题意：

给你一组数组 A=[5,3,4,5] 小六(先手)和小七轮流从里面取数字，但两人只能拿第一个或者最后一个数字，取完之后这数字会从 A 中移除，问谁是最后的赢家如果两个人每次都采取对自己最有利的方案。分数最多者为胜利者。

解题思路一、Top Down

对于每个 player 来说，他都有两种选择（以第一轮为例）：

1. 如果小六选了 A[0] ，那么他会留下 [3,4,5]  给小七做选择；
   
2. 如果他选的是 A[3] ，他会留下 [5,3,4] 给小七做选择。
   

如果我们选择暴力的方法的话，我们可以把所有的可能性都列举出来。

当某一个 player 选掉一个数字后，他可以把剩下的数字递归给下一位 player，当所有数字取完时，游戏结束。

这里我们可以得到一个观察，因为数字只能取第一个或者最后一个，我们可以用一个区间 [l,r] 去表达剩下的数字。

如果我们取第一个，新的 A 会变成 [l+1,r] ；如果我们取最后一个，新的 A 是 [l,r-1] 。

这就是我们所谓的状态压缩，我们用两个数字来表达数组的状态，这里的状态是指它还剩下哪些数字，而不是真的把数字从A里面移除掉，因为这样会导致很高的时间复杂度。

除此之外，我们还需要一个额外的 player variable 去记录当前是谁的回合 (不同的 player 会用不同的决策)。

以下是表达状态转移的代码（不完整），我们还需要对每个人采用的 决策 (博弈) 进行分析。

// 我们可以用以下来表达状态变化的简单的递归模式

 if (l==r) {// 如果只剩一个，直接取这一个

   returnA[l]；

   }

 intnextPlayer= (player+1) %2;

   intscore=0;

 score=Math.max(score, A[l] +play(A,l+1,r,nextPlayer )); // 如果取第一个数字

 score=Math.max(score, A[r] +play(A,l,r-1,nextPlayer )); // 如果取最后一个数字

 returnscore;

}

分析:

• 我们首先会重新定义 play 函数，play 函数的返回值是小六能拿的分数。如果最终这个分数在总分数一半以上的话，小六能获胜，反之，小七获胜或平手；
  
• 如果我是小六 ，对于返回来的分数选择中，有两个选择。身为小六，如果他想要拿到最多的分，他得选择最大的那一个；
  
• 如果我是小七，同样有两个选择。但跟小六不一样的是，小七会选择返回一个最小的数给小六因为她不想让小六获胜；
  
• 最终我们的代码将能用 dp[l][r][player] 去表达我们的压缩状态，[l,r] 就如之前所说，表示当前剩下的数字的范围，player 代表当前是谁的回合；
  
• 我们用 0 代表小六，1 代表小七。
  

完整代码 Top Down

classSolution {  

  intdp[][][];  

  publicbooleanstoneGame(int[] A) {  

      dp=newint[A.length][A.length][2];  

       intsum=0;  

      for(inti : A){  

          sum+=i;  

      }    

   

      intmaxScore=play(A,0,A.length-1,0);  

      returnmaxScore*2>sum;  

   }  

 

     publicintplay(intA[],intl,intr,intplayer){  

       if(l==r){// 数组为1

           returnA[l];  

       }  

       

       if(dp[l][r][player]!=0){ // 如果是已经访问过的状态，我们不需要再重新计算  

           returndp[l][r][player];  

       }  

 

       intnextPlayer= (player+1) %2; // 下一个player是谁？我们用0代表小六，1代表小七

       intscore=0;  

   

   // 我们可以从递归这里推导出关系式，从而转换成BottomUp

       if(player==0){ // 小六：对于返回的分数，我要取最大的那一个

           score=Math.max(score,A[l]+play(A,l+1,r,nextPlayer));  

           score=Math.max(score,A[r]+play(A,l,r-1,nextPlayer));  

       }  

       else{ // 小七：hmm，为了不让小六赢，我得返回一个最小的数字给小六

             // 这里不需要加A[l] 或者A[r]，因为play 函数是小六的分数

           score=Math.min(play(A,l+1,r,nextPlayer),play(A,l,r-1,nextPlayer));  

       }  

 

       dp[l][r][player] =score; // 对状态的值的储存

       returnscore;  

     }  

}

代码总结 ：

• play 函数就是我们的主要逻辑所在，play 函数值是小六能得到的最大分数。
  
• 我们用 [l,r] 去表示还剩下哪些数字，player 去表示当前的回合。nextPlayer是下一个回合。如果当前回合是0，下一个回合就是1。如果当前回合是1，下一个回合就是0。我们用 nextPlayer = (player + 1) % 2 。
  
• 我们有两种情况，player 是0和是1的情况。如果是0 (先手小六)，他想得到的是最大的分数，所以我们传回一个 max。如果是1（小七后手），她想要小六拿到最小，所以我们回传一个最小。  注意，小七的回合我们不用加上A[l] 或者A[r]，因为play是小六的分数，所以小七回合的A[l] 或者 A[r] 不用归入小六里面。
  

时空复杂度分析

空间复杂度就非常明显是 2 * O(N^2) 。

时间复杂度是 play 函数的状态个数乘每个play函数的时间复杂度。

我们一共有 2N^2 的状态，play函数的空间是 O(1)，所以时间复杂度也是 2 * O(N^2) 。 简化一下就是 O(N^2)。

• 空间复杂度：O(N^2)
  
• 时间复杂度：O(N^2)