leetcode之石子游戏(博弈类动态规划)

leetcode之石子游戏(博弈类动态规划)

  • 这是一道博弈类的动态规划题目,题目假设两者都能发挥出最佳水平,那么这题如果用贪心算法(每次选取最左边和最右边的最大值)其实是不行的,比如[1,100,3];不管先手一开始拿的是最左边的1还是最右边的3,那么后手都能拿到100,后手就会赢。所以这里我们采用动态规划去解决。

思路如下:(毕竟是动态规划,那我们就按照动态规划的三步来走)

  1. 首先就是定义状态dp[i][j],用来表示在i~j堆石子中,亚历克斯比李多拿的石子。一般来说动态规划,我们看看是不是很明显的二维动态数组,如果是的话我们先直接定义二维数组,然后到后面再去考虑状态压缩。
  2. 这里的状态转移方程比较难找,我们可以这样思考:
    2.1 如果这里只有两堆石子[3,5],我们怎么保证亚历克斯的dp[0][1]最优值? 如果亚历克斯一开始拿走的是piles[0]=3,此时李变成了先手,那么状态是不是变成了要找李的dp[1][1],(亚历克斯的最优选取策略就变成了李的最优选取策略)即dp[i+1][j]表示对手比当前的选手多出来的石子数量,那么此时亚历克斯比李多的石子数量就是“piles[0] - dp[1][1]”;同理,如果亚历克斯一开始拿走的是piles[1],那么此时李变成了先手,那么亚历克斯比李多的石子数量就是“piles[1] - dp[0][0]”,我们选取两者之间的最大值就好了。
    2.2 如果此时是三堆石子[3,5,1],我们可以同样这样思考,如果亚历克斯一开始拿走的是piles[0],那么是不是此时就该比较“piles[0] - dp[1][2]”;同理,如果亚历克斯一开始拿走的是piles[2],那么此时李变成了先手,那么亚历克斯比李多的石子数量就是“piles[2] - dp[0][1]”。
    3.3 以此类推,到n堆石子的时候,我们判断max(piles[0] - dp[1][n-1],piles[n-1] - dp[0][n-2])即可;
  3. 最后一步就是确定base case了,我们刚开始定义状态转移方程的时候,发现了如果只有i==j的时候,我么的dp[i][i]表示的就是亚历克斯比李多拿的石子,那么这个石子就是等于piles[i];所以我们的初始状态就是dp[i][i] = piles[i]。
  4. 附上代码:
class Solution {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[][] dp = new int[n][n];
        for(int i=0;i<n;i++){
            dp[i][i] = piles[i];
        }
        for(int len=1;len<n;len++){
            for(int i=0;i<n-len;i++){
                int j = i + len;
                dp[i][j] = Math.max(piles[i] - dp[i+1][j],piles[j] - dp[i][j-1]);
            }
        }
        return dp[0][n-1] > 0;
    }
}
  • 此时我们再来考虑状态压缩。我们发现在更新dp数组的时候,我们只是用到了对角线上的dp数组,而且我们更新的顺序是从左上角到右下角,并没有在更新一个dp元素的时候又更新了这个dp数组的左上角元素,所以我们可以使用一位数组来解决这个问题。
class Solution {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[] dp = new int[n];
        for(int i=0;i<n;i++){
            dp[i] = piles[i];
        }
        for(int len=1;len<n;len++){
            for(int i=0;i<n-len;i++){
                int j = i + len;
                dp[i] = Math.max(piles[i] - dp[i+1],piles[j] - dp[j-1]);
            }
        }
        return dp[n-1] > 0;
    }
}
上一篇:竞猜活动区块链方案探索


下一篇:【LeetCode】Powerful Integers(强整数)