1049. 最后一块石头的重量 II
文档和视频讲解:代码随想录(programmercarl.com)
状态:未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. 目标和
文档和视频讲解:代码随想录(programmercarl.com)
状态:未ac
用时:1h
思路:本题要如何使表达式结果为target,既然为target,那么就一定有 left组合 - right组合 = target。left + right = sum,而sum是固定的。right = sum - left。left - (sum - left) = target 推导出 left = (target + sum)/2 。target是固定的,sum是固定的,left就可以求出来。此时问题就是在集合nums中找出和为left的组合。
由于dp[0]是后面所有的结果的起源,如果初始化为0,则后面所有结果都会等于0,因此初始化为1。
代码:
474.一和零
文档和视频讲解:代码随想录(programmercarl.com)
状态:未ac
用时:1h
思路:
代码: