11 动态规划解最后一块石头的重量II

来源：LeetCode第1049题

难度：中等

描述：有一堆石头，用证书数组stones表示，其中stones[i]表示第i块石头的重量，每一回合，从中选出任意两块石头，然后将他们放在一起粉碎，假设石头的重量分别为x和y，且x<=y,那么可能粉碎的结果可能如下：
        如果x==y,那么两块石头会被完全粉碎
        如果x!=y,那么重量为x的石头将会完全被粉碎，而重量y的石头新重量为y-x，最后最多只剩下一块石头，最多只会剩下一块石头，返回此石头可能最小重量。

思路解析：该题可以看做是一个背包问题，将stones数组分为重量尽可能接近的两队，然后两队之间的差值即是此石头最后的重量，可以定义二维动态规划数组dp[i][j]表示从前i个元素中挑选出元素放入容量为j的背包所能达到的最大值，对于每个元素都可以选或者不选；

public int getLastStone(int []stones)
{
int sum=0;
for(int number:stones)
{
sum+=number;
}
int dp[][]=new int[stones.length][sum>>1];
dp[0][0]=0;
for(int i=1;i<stones.length;i++)
{
dp[i][0]=0;
}
for(int i=1;i<stones.length;i++)
{
for(int j=1;j<sum>>1;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][sum>>1]-sum);
}