怎么做asp网站,网站营销推广怎么做,淄博网站建设程序,wordpress 巨慢【动态规划】【01背包】Leetcode 1049. 最后一块石头的重量 II 解法 ---------------#x1f388;#x1f388;题目链接#x1f388;#x1f388;-------------------
解法
#x1f612;: 我的代码实现
动规五部曲
✒️确定dp数组以及下标的含义 dp[j]表示容量为… 【动态规划】【01背包】Leetcode 1049. 最后一块石头的重量 II 解法 ---------------题目链接-------------------
解法
: 我的代码实现
动规五部曲
✒️确定dp数组以及下标的含义 dp[j]表示容量为j的背包最多可以背最大重量为dp[j]。 ✒️确定递推公式 01背包的递推公式为dp[j] max(dp[j], dp[j - weight[i]] value[i]); 本题则是——dp[j] max(dp[j], dp[j - stones[i]] stones[i]) ✒️dp数组初始化 初始为0即可 ✒️确定遍历顺序 正序遍历物品倒序遍历背包 最后dp[target]里是容量为target的背包所能背的最大重量。 ⭐️那么求dp[sum/2] 即dp[target]即可 那么分成两堆石头一堆石头的总重量是dp[target]另一堆就是sum - dp[target]。 时间复杂度O(N) 空间复杂度O(N)
代码
class Solution {public int lastStoneWeightII(int[] stones) {// 得到总的重量int sum 0;for(int stone:stones){sum stone;}// 希望尽可能凑出离total/2近的两组石头 》 一组离total/2近 那另一组也一定离total/2近// dp[j] : 装满容量为j的背包 能装下的最大重量为dp[j] int total sum/2;int[] dp new int[total1];for(int i 0 ; i stones.length; i){ // 正序遍历物品for(int j total; jstones[i]; j--){ // 倒序遍历背包dp[j] Math.max(dp[j] , dp[j-stones[i]]stones[i]);}}for(int j 0; j total; j){ // 倒叙遍历背包System.out.println(dp[j]);}return Math.abs(dp[total] - (sum-dp[total]));}
}
