代碼隨想錄算法訓練營第四十三天 | 474. 一和零、494. 目標和、1049. 最后一塊石頭的重量 II

474. 一和零

題目鏈接：474. 一和零

  • 這里因為0和1的數(shù)量不同，所以dp數(shù)組的重量由兩個數(shù)表示，二維數(shù)組

  • 接著就是套公式

494. 目標和

題目鏈接：494. 目標和

  • 給一個容量，問有多少種方式能把背包裝滿

  • d p[j]：裝滿容量為j的背包有dp[j]種方法

  • 比如說已經(jīng)有了一個2，還需要dp[3]種方法可以

  • 遞推公式：dp[j] = dp[j - nums[j]]

  • 初始化： dp[0] = 1

  • 求多少種方法都是這個遞推公式

1049. 最后一塊石頭的重量 II

題目鏈接：1049. 最后一塊石頭的重量 II

  • 和分割等和子集類似，因為這里的石頭的重量和價值是等價的，求最大價值就是試圖將背包填滿

  • dp數(shù)組長度為sum/2

  • 可以用移位運算符來進行除二操作

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容