1049.?最后一塊石頭的重量?II?
文檔和視頻講解：代碼隨想錄(programmercarl.com)
狀態(tài)：未ac
用時：1h
思路：盡量把石頭分成兩堆相等的咧叭，這樣碰撞出來的石頭最小，甚至沒有烁竭。那就可以化成一個01背包問題菲茬，其物品重量weight[i]和物品價值value[i]都是石頭重量。
取一個target作為石頭總重量的一半（可以不整除派撕，向下取整）婉弹。dp[target]表示target的背包容量中最多可以裝 的石頭重量，也就是最接近target的终吼。最后分成兩堆石頭镀赌，一堆石頭的總重量是dp[target]，另一堆就是sum - dp[target]际跪。
在計算target的時候商佛，target = sum / 2 因為是向下取整喉钢，所以sum - dp[target] 一定是大于等于dp[target]的。那么相撞之后剩下的最小石頭重量就是 (sum - dp[target]) - dp[target]良姆。
代碼：
494.?目標(biāo)和?
文檔和視頻講解：代碼隨想錄(programmercarl.com)
狀態(tài)：未ac
用時：1h
思路：本題要如何使表達(dá)式結(jié)果為target肠虽，既然為target，那么就一定有 left組合 - right組合 = target歇盼。left + right = sum舔痕，而sum是固定的。right = sum - left豹缀。left - (sum - left) = target 推導(dǎo)出 left = (target + sum)/2 伯复。target是固定的，sum是固定的邢笙，left就可以求出來啸如。此時問題就是在集合nums中找出和為left的組合。
由于dp[0]是后面所有的結(jié)果的起源氮惯，如果初始化為0叮雳，則后面所有結(jié)果都會等于0，因此初始化為1妇汗。
代碼：
474.一和零??
文檔和視頻講解：代碼隨想錄(programmercarl.com)
狀態(tài)：未ac
用時：1h
思路：
代碼：
