- 这是一道博弈类的动态规划题目,题目假设两者都能发挥出最佳水平,那么这题如果用贪心算法(每次选取最左边和最右边的最大值)其实是不行的,比如[1,100,3];不管先手一开始拿的是最左边的1还是最右边的3,那么后手都能拿到100,后手就会赢。所以这里我们采用动态规划去解决。
思路如下:(毕竟是动态规划,那我们就按照动态规划的三步来走)
- 首先就是定义状态dp[i][j],用来表示在i~j堆石子中,亚历克斯比李多拿的石子。一般来说动态规划,我们看看是不是很明显的二维动态数组,如果是的话我们先直接定义二维数组,然后到后面再去考虑状态压缩。
- 这里的状态转移方程比较难找,我们可以这样思考:
2.1 如果这里只有两堆石子[3,5],我们怎么保证亚历克斯的dp[0][1]最优值? 如果亚历克斯一开始拿走的是piles[0]=3,此时李变成了先手,那么状态是不是变成了要找李的dp[1][1],(亚历克斯的最优选取策略就变成了李的最优选取策略)即dp[i+1][j]表示对手比当前的选手多出来的石子数量,那么此时亚历克斯比李多的石子数量就是“piles[0] - dp[1][1]”;同理,如果亚历克斯一开始拿走的是piles[1],那么此时李变成了先手,那么亚历克斯比李多的石子数量就是“piles[1] - dp[0][0]”,我们选取两者之间的最大值就好了。
2.2 如果此时是三堆石子[3,5,1],我们可以同样这样思考,如果亚历克斯一开始拿走的是piles[0],那么是不是此时就该比较“piles[0] - dp[1][2]”;同理,如果亚历克斯一开始拿走的是piles[2],那么此时李变成了先手,那么亚历克斯比李多的石子数量就是“piles[2] - dp[0][1]”。
3.3 以此类推,到n堆石子的时候,我们判断max(piles[0] - dp[1][n-1],piles[n-1] - dp[0][n-2])即可; - 最后一步就是确定base case了,我们刚开始定义状态转移方程的时候,发现了如果只有i==j的时候,我么的dp[i][i]表示的就是亚历克斯比李多拿的石子,那么这个石子就是等于piles[i];所以我们的初始状态就是dp[i][i] = piles[i]。
- 附上代码:
class Solution {
public boolean stoneGame(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<n-len;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;
}
}
- 此时我们再来考虑状态压缩。我们发现在更新dp数组的时候,我们只是用到了对角线上的dp数组,而且我们更新的顺序是从左上角到右下角,并没有在更新一个dp元素的时候又更新了这个dp数组的左上角元素,所以我们可以使用一位数组来解决这个问题。
class Solution {
public boolean stoneGame(int[] piles) {
int n = piles.length;
int[] dp = new int[n];
for(int i=0;i<n;i++){
dp[i] = piles[i];
}
for(int len=1;len<n;len++){
for(int i=0;i<n-len;i++){
int j = i + len;
dp[i] = Math.max(piles[i] - dp[i+1],piles[j] - dp[j-1]);
}
}
return dp[n-1] > 0;
}
}