专栏名称: 九章算法

专业的北美IT求职经验分享、技术交流社区，帮助你找到好的IT工作。由硅谷顶尖IT企业工程师维护。提供专业的算法培训/面试咨询，官网 www.jiuzhang.com

面试题解| coins in a line iii 区间DP

九章算法 · 公众号 · 算法 · 2018-05-28 23:41

正文

题

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的区间转化而来的。

问题2

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

定义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 here
int 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;
}
}
}

面试题解| coins in a line iii 区间DP

正文

请到「今天看啥」查看全文