https://leetcode.cn/problems/last-stone-weight-ii/submissions/578565322/

通过观察，可以把石头分成两个总量近乎相等集合，两个集合之间的石头碰，最后的答案就是两个集合的差值，所以要在数组找一个子序列，值要接近数组总和的一半才是最优

int a[110];
int dp[100010];
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int n=stones.size();
        int ans=0;
        a[0]=0;

        for(int i=1;i<=n;i++) a[i]=stones[i-1],ans+=a[i];
                for(int i=0;i<=ans;i++) dp[i]=0;

        int k=ans/2;
        for(int i=1;i<=n;i++)
        {
            for(int j=k;j>=a[i];j--)
            {
                dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
            }
        }
        int ok=ans-dp[k];
        return abs(dp[k]-ok);


    }
};