01背包問(wèn)題
分為二維數(shù)組和一維數(shù)組，一維有點(diǎn)繞
416.?分割等和子集
動(dòng)規(guī)五部曲：
確定dp數(shù)組以及下標(biāo)的含義
01背包中羽资，dp[j] 表示： 容量為j的背包，所背的物品價(jià)值最大可以為dp[j]遵班。
dp[j]表示 背包總?cè)萘浚ㄋ苎b的總重量）是j屠升，放進(jìn)物品后，背的最大重量為dp[j]
如果背包容量為target狭郑， dp[target]就是裝滿 背包之后的重量腹暖，所以 當(dāng) dp[target] == target 的時(shí)候，背包就裝滿了
確定遞推公式
01背包的遞推公式為：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
dp數(shù)組如何初始化
dp[0]一定是0
確定遍歷順序
使用一維dp數(shù)組翰萨，物品遍歷的for循環(huán)放在外層脏答，遍歷背包的for循環(huán)放在內(nèi)層，且內(nèi)層for循環(huán)倒序遍歷
// 開(kāi)始 01背包for(inti=0;i<nums.size();i++){for(intj=target;j>=nums[i];j--){// 每一個(gè)元素一定是不可重復(fù)放入，所以從大到小遍歷dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);}}
