我要评论一、题目描述
题目链接：https://leetcode-cn.com/problems/stone-game/
二、题目分析
可以使用搜索的方法来解决。对于每次操作，都有两个选择，拿最左边的石堆或者拿最右边的石堆，剩下的可以到下一层递归，而且这里是可以使用memo优化的，因为先拿左边再拿右边，和先拿右边再拿左边是等价的。
三、代码
private Integer[][] memo;
public boolean stoneGame(int[] piles) {
memo = new Integer[piles.length][piles.length];
int sum = 0;
for (int num: piles) {
sum += num;
}
int res = stoneHelper(piles,0,piles.length-1);
return res > (sum - res);
}
private int stoneHelper(int[] piles, int left, int right) {
if (left == right) return piles[left];
if (memo[left][right] != null) return memo[left][right];
int pickLeft = piles[left] + stoneHelper(piles,left+1,right);
int pickRight = piles[right] + stoneHelper(piles,left,right-1);
return memo[left][right] = Math.max(pickLeft,pickRight);
}
本文地址：https://blog.csdn.net/ykben/article/details/107313816
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论