专栏 | 九章算法

网址 | http://www.jiuzhang.com

题 coins in a line iii 区间DP

有 n 个硬币排成一条线，每一枚硬币有不同的价值。两个参赛者轮流从任意一边取一枚硬币,直到没有硬币为止。计算拿到的硬币总价值，价值最高的获胜。 请判定 第一个玩家 是输还是赢？

给定数组 A = [3,2,2], 返回 true.
给定数组 A = [1,2,4], 返回 true.
给定数组 A = [1,20,4], 返回 false.
复制代码

本题我们需要定义dp(i,j)为区间(i,j)先手玩家可以取到的最大硬币总价值。

如何定义sum(i,j)是从i到j的区间和呢？

• 首先考虑dp(i,j),可以拿第i个硬币，从dp(i+1,j)转移过来。也可以拿第j个硬币，从第dp(i,j-1)转移过来。

• dp方程为dp(i,j) = max(values[i] + sum(i+1,j) - dp(i+1,j) , values[j] + sum(i,j-1) - dp(i,j-1));

• 其中的values[i] + sum(i+1,j) - dp(i+1,j) 可以这样理解：我拿第i个数值，values[i]是我拿到的数值，肯定要加上，再想区间(i+1,j)我能拿到的最大值是多少，由于我拿了第i个，所以区间(i+1,j)变成了对面先手，对面能够拿到最大值dp(i+1,j)，而我只能拿到sum(i+1,j)-dp(i+1,j)

• 由上述公式就可以写出代码了，时间复杂度O(N^2)，空间复杂度O(N^2)

• 可以使用滚动数组的方法对空间进行优化，达到O(N)的空间复杂度。

之前的那个公式对于写代码来说并不是很直观，注意到，上述公式dp(i,j)区间长度为j-i+1，dp(i,j-1) 和dp(i+1,j)的区间长度都是j-i，考虑到区间长度为j-i+1的区间是由区间长度为j-i的区间转化而来的。

如何更好的转化上述公式呢？

• 定义k为一个区间的长度。

• 则上述公式可以写作dp(i,i+k) = max(values[i] + sum(i+1,i+k) - dp(i+1,i+k) , values[i+k] + sum(i,i+k-1) - dp(i,i+k-1))

• 现在将dp的第二维定义为这个区间的长度，所以dp(i,k)的含义变成了区间(i,i+k)先手玩家可以取到的最大硬币总价值。

• 上述公式变为dp(i,k) = max(values[i] + sum(i+1,i+k) - dp(i+1,k-1) , values[i+k] + sum(i,i+k-1) - dp(i,k-1))

• 由上述的公式可以很容易的写出代码了，时间复杂度O（N^2），空间复杂度O(N^2)

• 其实空间复杂度还是可以优化的，第一种方法：可以滚动数组，可以把空间复杂度变为O(N)。第二种方法：与背包算法的空间优化类似，将i变成从后向前找，空间复杂度为O(N)，这个比前面一种优化方法，常数小一些。

• 公式变为 dp1(i) = max(values[i] + sum(i+1,i+k) - dp1(i+1) , values[i+k] + sum(i,i+k-1) - dp1(i)) i 从后向前遍历

• 这里有一个问题，dp1(i+1)这个值在计算dp1(i+1)的时候被改变了，但是在计算dp1(i)之中又用到了，所以在改变之前需要存储这个值。

• 时间复杂度O(N^2),空间复杂度O(N)。代码如下：

public class Solution {/*** @param values: an array of integers* @return: a boolean which equals to true if the first player will win*/public boolean firstWillWin(int[] values) {// write your code hereint len = values.length;int [] sum = new int[len+1]; //int [][] dp = new int[len][len];int [] dp1 = new int[len];sum[0] = 0;for (int i = 1 ; i <= len ; i ++) {sum[i] = sum[i-1] + values[i-1];}// Init dp(i,0) = values[i] for (int i = 0 ; i < len ; i ++) {//dp[i][0] = values[i];dp1[i] = values[i];}int tmp = 0;for (int k = 1 ; k < len ; k ++) {tmp = dp1[len-k];for (int i = len - k - 1 ; i >= 0 ; i --) {// sum(i) = add from index 0 to i-1// sum(i,j) = sum(j+1) - sum(i) // sum(i+1,i+k) = sum(i+k+1) - sum(i+1)// sum(i,i+k-1) = sum(i+k) - sum(i)// dp[i][k] = Math.max(values[i] + (sum[i+k+1] - sum[i+1]) - dp[i+1][k-1], values[i+k] + (sum[i+k] - sum[i]) - dp[i][k-1]);int tmp1 = dp1[i];dp1[i] = Math.max(values[i] + (sum[i+k+1] - sum[i+1]) - tmp, values[i+k] + (sum[i+k] - sum[i]) - dp1[i]);tmp = tmp1;}}if(dp1[0] * 2 > sum[len]) {return true;}else {return false;}}
}
复制代码

这里有一个问题，dp1(i+1)这个值在计算dp1(i+1)的时候被改变了，但是在计算dp1(i)之中又用到了，所以在改变之前需要存储这个值。

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

这道题是一个动态规划的问题，给出动态规划算法可以hire。优化空间到O(N)可以达到strong hire。