0. 前言
秋招字节笔试题有一类似该题的算法题,正解应该使用动态规划。
1. 题目
Alex and Lee play a game with piles of stones. There are an even number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].
The objective of the game is to end with the most stones. The total number of stones is odd, so there are no ties.
Alex and Lee take turns, with Alex starting first. Each turn, a player takes the entire pile of stones from either the beginning or the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.
Assuming Alex and Lee play optimally, return True if and only if Alex wins the game.
简单来说:有一排偶数堆石头,石头的总数为奇数,Alex和Lee每次取走头或尾的一堆,如果Alex和Lee都采用最佳方法,问先手的Alex是否能赢?
2. 解一:递归
依题意分情况递归,使用一个变量player记录当前是谁拿石头堆,使用cur0和cur1记录Alex和Lee当前的石头总数,同时使用头尾指针记录当前取到拿
代码如下:1
2
3
4
5
6
7
8
9
10
11
12public static boolean stoneGame(int[] piles, int cur0, int cur1, int left, int right, int player) {
if (left > right) {
return cur0 > cur1;
}
if (player == 0) {
return stoneGame(piles, cur0 + piles[left], cur1, left + 1, right, 1)
|| stoneGame(piles, cur0 + piles[right], cur1, left, right - 1, 1);
} else {
return stoneGame(piles, cur0, cur1 + piles[left], left + 1, right, 0)
|| stoneGame(piles, cur0, cur1 + piles[right], left, right - 1, 0);
}
}
但是,上述代码存在漏洞,没有考虑到双方都采用最佳方法,只是对所有情况进行递归判断,只要有存在一种情况能让Alex赢就算是Alex赢。
简单的对头尾大小进行判断而选取的局部最优策略是不对的,要双方都使用最佳策略,则应该使用动态规划从小到大计算dp数组。
除去时间复杂度的影响,上述代码能通过LeetCode,是有原因的,具体可以参考解三。
3. 解二:动态规划
本文的重点就是动态规划的解法,因为当时的笔试题要求算的是Alex最多能拿多少个石头,而不是能否赢Lee。
dp数组
把一排的石头堆看成一维数轴,设dp[i][j]表示在区间 [i, j] 内 Alex 比 Lee 多拿的石子数,
若为正数,说明 Alex 拿得多,若为负数,则表示 Lee 拿得多。
事实上所使用到的空间只有整个二维数组的一半(左对角线的右侧),最终结果就是dp[0][n - 1] > 0
由于双方都采用最佳策略,dp[i][j]是双向的,应该理解到,若dp[i][j]表示在区间 [i, j] 内 Alex 比 Lee 多拿的石子数
那么dp[i + 1][j]表示在区间 [i + 1, j] 内 Lee 比 Alex 多拿的石子数,
dp[i][j - 1]表示在区间 [i, j - 1] 内 Lee 比 Alex 多拿的石子数
初始状态
dp[i][i] = piles[i], 0 <= i < n
状态转移方程
因为可以从头尾选取一堆,理解了dp数组的含义后,可以得出,
若取头,dp[i][j] = piles[i] - dp[i + 1][j];若取尾,dp[i][j] = piles[j] - dp[i][j - 1]
因此,dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14public static boolean stoneGame_DP(int[] piles) {
int n = piles.length;
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
dp[i][i] = piles[i];
}
for (int len = 1; len < n; len++) {
for (int i = 0; i + len < n; i++) {
int j = i + len;
dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
}
}
return dp[0][n - 1] > 0;
}
4. 解三:题设利用
根据已知条件,可以知道没有平局。对每一堆石头进行编号,从1开始到n。如果按奇偶分成两部分,一定其中一部分石头总数大,另一部分小。
这么就好办了,如果奇数堆总数大,因为Alex先手,那么Alex可以每次都取奇数序号的石头堆;同理,如果偶数堆总数大,因为Alex先手,那么Alex可以每次都取偶数序号的石头堆。最终Alex一定能赢。
结论:先手必胜。
5. 总结
本文关键是动态规划,但也应该懂得,有时候正确理解、利用题设条件是解题的快捷途径。
本文参考了以下文章:
Copyright © 2018, GDUT CSCW back-end Kanarien, All Rights Reserved