阿里云网站建设教程2017,js做的网站,邢台信息港首页,吉林网站备案来源#xff1a;LeetCode第1049题
难度#xff1a;中等
描述#xff1a;有一堆石头#xff0c;用证书数组stones表示#xff0c;其中stones[i]表示第i块石头的重量#xff0c;每一回合#xff0c;从中选出任意两块石头#xff0c;然后将他们放在一起粉碎#xff0c;…来源LeetCode第1049题
难度中等
描述有一堆石头用证书数组stones表示其中stones[i]表示第i块石头的重量每一回合从中选出任意两块石头然后将他们放在一起粉碎假设石头的重量分别为x和y且xy,那么可能粉碎的结果可能如下 如果xy,那么两块石头会被完全粉碎 如果x!y,那么重量为x的石头将会完全被粉碎而重量y的石头新重量为y-x最后最多只剩下一块石头最多只会剩下一块石头返回此石头可能最小重量。
思路解析该题可以看做是一个背包问题将stones数组分为重量尽可能接近的两队然后两队之间的差值即是此石头最后的重量可以定义二维动态规划数组dp[i][j]表示从前i个元素中挑选出元素放入容量为j的背包所能达到的最大值对于每个元素都可以选或者不选
public int getLastStone(int []stones)
{
int sum0;
for(int number:stones)
{
sumnumber;
}
int dp[][]new int[stones.length][sum1];
dp[0][0]0;
for(int i1;istones.length;i)
{
dp[i][0]0;
}
for(int i1;istones.length;i)
{
for(int j1;jsum1;j)
{
if(stones[i]j)
{
dp[i][j]Math.max(dp[i-1][j],dp[i-1][j-stones[i]]stones[i]);
}else
{
dp[i][j]dp[i-1][j];
}
}
}
return Math.abs(dp[stones.length-1][sum1]-sum);
}
相关文章：
