杭州手机网站制作电脑公司,如何免费创建个人网站,如何判断网站开发语言,手机免费注册网站1049. 最后一块石头的重量 II 核心思想#xff1a; 尽量让石头分成重量相同的两堆#xff0c;相撞之后剩下的石头最小#xff0c;这样就化解成01背包问题了。 是不是感觉和昨天讲解的416. 分割等和子集 (opens new window)非常像了。那么分成两堆石头#xff0c;一堆石头的…1049. 最后一块石头的重量 II 核心思想 尽量让石头分成重量相同的两堆相撞之后剩下的石头最小这样就化解成01背包问题了。 是不是感觉和昨天讲解的416. 分割等和子集 (opens new window)非常像了。那么分成两堆石头一堆石头的总重量是dp[target]另一堆就是sum - dp[target]。
class Solution {public int lastStoneWeightII(int[] stones) {int sum0;for(int i0;istones.length;i){sumstones[i];}int targetsum/2;int dp[]new int[target1];//1、定义dp数组 3、第一列初始化为0for(int i0;istones.length;i){for(int jtarget;jstones[i];j--){//4、遍历顺序dp[j]Math.max(dp[j],dp[j-stones[i]]stones[i]);//2.递推公式}}return sum-dp[target]-dp[target];//最终的返回结果}
}时间复杂度O(m × n) , m是石头总重量准确的说是总重量的一半n为石头块数 空间复杂度O(m)
494. 目标和 思路 这道题的dp数组的含义变了。具体看代码随想录的讲解
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum0;for(int i0;inums.length;i){sumnums[i];}//如果不能满足(targetsum)/2为整数的条件或target的绝对值大于sum的绝对值直接返回0if((targetsum)%2!0 || Math.abs(target)Math.abs(sum)) return 0;int size(targetsum)/2;int[] dpnew int[size1];//1、定义dp数组表示j容量时的表达式数目dp[0]1;//3、初始化for(int i0;inums.length;i){for(int jsize;jnums[i];j--){//4、因为是01背包所以反向遍历dp[j]dp[j]dp[j-nums[i]];//2、递推公式}}return dp[size];}
}时间复杂度O(n × m)n为正数个数m为背包容量 空间复杂度O(m)m为背包容量
474.一和零 思路 这道题是一个二维的背包问题和普通的背包相比只需要多一层对容量的循环。
class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dpnew int[m1][n1];//1、定义dp数组表示当0的容量为x1的容量为n时最大子集的长度for(int i0;istrs.length;i){//4、遍历顺序物品正序遍历int weightm0;int weightn0;for(int j0;jstrs[i].length();j){if(strs[i].charAt(j)0) weightm; else weightn;}for(int xm;xweightm;x--){//4、物品的空间占用逆序遍历for(int yn;yweightn;y--){dp[x][y]Math.max(dp[x][y],dp[x-weightm][y-weightn]1);//2、递推公式注意value是1}}}return dp[m][n];}
}时间复杂度: O(kmn)k 为strs的长度 空间复杂度: O(mn)
