专栏 | 九章算法
网址 | 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的区间转化而来的。
问题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;
}
}
}
这里有一个问题,dp1(i+1)这个值在计算dp1(i+1)的时候被改变了,但是在计算dp1(i)之中又用到了,所以在改变之前需要存储这个值。
时间复杂度O(N^2),空间复杂度O(N)
面试官角度分析
这道题是一个动态规划的问题,给出动态规划算法可以hire。优化空间到O(N)可以达到strong hire。
欢迎关注我的微信公众号:九章算法(ninechapter)。
精英程序员交流社区,定期发布面试题、面试技巧、求职信息等