代码随想录算法训练营第四十三天 | 474. 一和零、494. 目标和、1049. 最后一块石头的重量 II

474. 一和零

题目链接:474. 一和零

  • 这里因为0和1的数量不同,所以dp数组的重量由两个数表示,二维数组

  • 接着就是套公式

494. 目标和

题目链接:494. 目标和

  • 给一个容量,问有多少种方式能把背包装满

  • d p[j]:装满容量为j的背包有dp[j]种方法

  • 比如说已经有了一个2,还需要dp[3]种方法可以

  • 递推公式:dp[j] = dp[j - nums[j]]

  • 初始化: dp[0] = 1

  • 求多少种方法都是这个递推公式

1049. 最后一块石头的重量 II

题目链接:1049. 最后一块石头的重量 II

  • 和分割等和子集类似,因为这里的石头的重量和价值是等价的,求最大价值就是试图将背包填满

  • dp数组长度为sum/2

  • 可以用移位运算符来进行除二操作

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容