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

708 阅读4分钟

专栏 | 九章算法

网址 | 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)。
精英程序员交流社区,定期发布面试题、面试技巧、求职信息等
2d09fefd332a1a68bb1c.jpeg