java算法day43 | 动态规划part05 ● 1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零

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

核心思想： 尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。
是不是感觉和昨天讲解的416. 分割等和子集 (opens new window)非常像了。那么分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。

class Solution {public int lastStoneWeightII(int[] stones) {int sum=0;for(int i=0;i<stones.length;i++){sum+=stones[i];}int target=sum/2;int dp[]=new int[target+1];//1、定义dp数组 3、第一列初始化为0for(int i=0;i<stones.length;i++){for(int j=target;j>=stones[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 sum=0;for(int i=0;i<nums.length;i++){sum+=nums[i];}//如果不能满足(target+sum)/2为整数的条件或target的绝对值大于sum的绝对值，直接返回0if((target+sum)%2!=0 || Math.abs(target)>Math.abs(sum)) return 0;int size=(target+sum)/2;int[] dp=new int[size+1];//1、定义dp数组，表示j容量时的表达式数目dp[0]=1;//3、初始化for(int i=0;i<nums.length;i++){for(int j=size;j>=nums[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[][] dp=new int[m+1][n+1];//1、定义dp数组，表示当0的容量为x，1的容量为n时，最大子集的长度for(int i=0;i<strs.length;i++){//4、遍历顺序，物品正序遍历int weightm=0;int weightn=0;for(int j=0;j<strs[i].length();j++){if(strs[i].charAt(j)=='0') weightm++; else weightn++;}for(int x=m;x>=weightm;x--){//4、物品的空间占用逆序遍历for(int y=n;y>=weightn;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)