动态规划

关于什么是动态规划，这里不再赘述，网上有大把教程和概念，阅读本文前提是你对动态规划已经有了初步的认识。

概括来说，动态规划有四个步骤：

1. 定义状态。
2. 寻找状态转移方程
3. 状态压缩（如果可行的话）
4. 得出结果

LeetCode上的猜石子游戏

LeetCode有很多猜石子的游戏，大多是角色都能发挥最优的水平，属于博弈的范畴，下面就介绍三道可以用动态规划来解决的猜石子题目，难度也有容易用困难。

1、LeetCode486：预测赢家

题目描述

思考过程

1、从题目中可以看出，玩家每次只能从数组的头尾取出数字（石子），但是取头部还是尾部是随意的。

数组取完之后，两个人都会有一个得分，玩家1得分与玩家2得分差可以用来作为判断谁成为赢家的依据。

2、定义状态dp[i][j]为，当前数组区间i,j时，两个人取完石子后的得分差的最大值。那么玩家只有两种选择，要么取第 i 的数字（头部），要么取第 j 位的数字（尾部）。下面分开讨论：

• 当玩家取第 i 位的数字的话，那么留给下一个玩家的区间就是[i+1,j]（闭区间），正好可以对应dp[i+1][j]的状态，故差值就是nums[i]-dp[i+1][j]。
• 当玩家取第 j 位的数字的时候，同理差值就是nums[j]-dp[i][j-1].

综上所述状态转移方程就是：

dp[i][j] = max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])

值得注意的是dp[i][j]的状态需要用到dp[i+1][j]的状态，故遍历数组的区间的时候，应该逆序遍历。

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        n=len(nums)
        dp=[[0]*n for _ in range(n)]  #dp[i][j]表示区间为[i,j]时候的得分差
        for i in range(n):
            dp[i][i]=nums[i] # 状态初始化，当区间长度只有1的时候，差值就是该值
        for i in range(n-2,-1,-1):
            for j in range(i+1,n):
                dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])
        return dp[0][n-1]>=0

2、LeetCode877、石子游戏

题目描述

解答

1、这题几乎和上一个预测玩家一模一样，或者更严谨地说，这是上一题的一个特例，即数组长度是偶数，数组和是奇数，经过证明其实会发现，这是一个先手必赢的问题，直接返回这题就解决了。证明过程略。

return True

2、但是细想一下，万一下次题目问的是，两个人博弈之后，所取得分数的分差最大能是多少，就不能这么写了，恰巧后面就有这么一道题目。

3、这题的代码和上一题一模一样，动态规划的思考过程也是一样。

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n=len(piles)
        dp=[[0]*n for _ in range(n)]  #dp[i][j]表示区间为[i,j]时候的得分差
        for i in range(n):
            dp[i][i]=piles[i]
        for i in range(n-2,-1,-1):
            for j in range(i+1,n):
                dp[i][j]=max(piles[i]-dp[i+1][j],piles[j]-dp[i][j-1])
        return dp[0][n-1]>=0

对吧，一模一样。

3、LeetCode1690、石子游戏VII

题目描述

思考过程

1、其实这一题和上一题也很相似，唯一不同的就是，所得的分数是取完当前数字剩余数字的总和。

涉及到频繁计算某个区间的和，且区间内的数字不发生改变，很自然想到前缀和数组。

假如一个数组是[1,2,3,5,8]，那么它的前缀和数组就是[0,1,3,6,11,19]，比原来数组长度长一位，那么计算nums[i:j]之间的和只需要用presum[j+1]-presum[i]就可以了。

比如计算nums[1]+nums[2]+nums[3]的和，只需要用presum[4]-presum[1]=10即可。

关于前缀和的具体原理这里也不做赘述，前缀和和差分数组日后有机会再详细写。

2、这题的状态定义与之前相同，需要改一下状态转移方程，将得分从nums[i]改成sum([i+1:j])就好了。

dp[i][j] = max(sum(stones[i+1:j])-dp[i+1][j],sum(stones[i:j-1])-dp[i][j-1])

计算sum的过程不用前缀和会浪费很多额外时间。

3、直接上代码，和前两题的代码除去前缀和完全一样

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        n = len(stones)
        presum = [0] + list(itertools.accumulate(stones))  # 计算前缀和，也可以一次遍历数组来求
        # presum = [0]*(n+1)
        # for i in range(1,n+1):
        #     presum[i] = presum[i-1]+stones[i-1]
        dp = [[0]*n for _ in range(n)]
        for i in range(n-2,-1,-1): # 因为i的状态与i+1有关，所以应该倒叙，且要比j小
            for j in range(i+1,n):
                l = presum[j+1] - presum[i+1]
                r = presum[j] - presum[i]
                dp[i][j] = max(l-dp[i+1][j],r-dp[i][j-1])
        return dp[0][n-1]

这就是动态规划在部分猜石子游戏中的应用，当然肯定还有一些猜石子游戏我没有写到。

最重要的我觉得是这三道题给我提供了一个思路，即将dp[i][j]定义成一个区间内的一个状态，然后通过不停地更新区间来更新状态，最后得到我们想要的结果。