這道題第一想法是用回溯，但是容易超時。

第二種是轉(zhuǎn)換為0-1背包問題

????????//若負(fù)數(shù)的和為neg,則整數(shù)的和為sum-neg

????????//按題目要求target?=?(sum-neg)-neg,轉(zhuǎn)換為neg?=?(sum-tar)/2

????????//dp[i][j]表示前i個元素，湊出和為j的方案數(shù)目

????????//當(dāng)i=0,j=0時方案數(shù)dp[0][0]=1,j>0時，dp[i][j]=0;

????????//其余情況中，j<num時，dp[i][j]=dp[i-1][j];j>=num時，dp[i][j]?=?dp[i-1][j]+dp[i-1][j-num]

還要注意一點(diǎn)就是，由于數(shù)組 nums中的元素都是非負(fù)整數(shù)，neg也必須是非負(fù)整數(shù)，所以上式成立的前提是 sum?target是非負(fù)偶數(shù)。若不符合該條件可直接返回 0。

題目

回溯法

動態(tài)規(guī)劃

降維

題目

同樣是轉(zhuǎn)換為0-1背包問題，背包的容量是sum/2，越接近這個值，最后剩下的石頭重量越低，是res = sum - 2*dp[len][mid]

code