算法笔记|Day31动态规划IV

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

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

题目分析

此题可以将stones分成两个总和最接近的两个部分，作差即为求得的最小值。若想使两部分最接近，第一部分的总和的目标应设置为target=sum/2，其中sum为集合中各个元素的和。这样可以得到的第一部分最大的总和为dp[target]，第二部分的总和为sum-dp[target]，差为(sum-dp[target])-dp[target]=sum-dp[target]*2。（注意点dp[target]总是小于target，而target小于等于sum/2）
1.dp数组含义：dp[j]表示总重量不超过j的几个数和的最大值（相当于0-1背包问题中的容量为j的背包最大的价值总和）；
2.递推公式：dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i])（相当于集合中每个元素的weight和value相同，都是数值stones）；
3.初始化：dp[0]=0；
4.遍历顺序：先遍历stones嵌套遍历背包，背包一定是要倒序遍历。

代码

class Solution {public int lastStoneWeightII(int[] stones) {int sum=0;for(int stone:stones)sum+=stone;int target=sum/2;int dp[]=new int[target+1];for(int i=0;i<stones.length;i++){for(int j=target;j>=stones[i];j--)dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);}return sum-dp[target]*2;}
}

☆☆☆☆☆leetcode 494.目标和

题目链接：leetcode 494.目标和

题目分析

此题可以将nums分成两个两个部分，第一部分为+号，第二部分为-号。记第一部分的总和为left，第二部分的总和为right，注意点应该有left+right=sum①，left-right=target②，这样可以得到第一部分的和为left=(sum+target)/2。考虑若sum+target为奇数或者sum+target<0，则一定没有元素符合题意，返回0。
1.dp数组含义：dp[j]表示填满容量为j（包括j）背包的方法数量；
2.递推公式：dp[j]+=dp[j-nums[i]]
（以dp[j]其中j为5举例，要想填满容量为5的背包，要考虑以下情况：
已经有一个1（nums[i]）的话，有dp[4]种方法凑成容量为5的背包。
已经有一个2（nums[i]）的话，有dp[3]种方法凑成容量为5的背包。
已经有一个3（nums[i]）的话，有dp[2]种方法凑成容量为5的背包
已经有一个4（nums[i]）的话，有dp[1]种方法凑成容量为5的背包
已经有一个5（nums[i]）的话，有dp[0]种方法凑成容量为5的背包
那么凑整dp[5]的总方法数也就是把所有的dp[j - nums[i]]累加起来）；
3.初始化：dp[0]=1；（考虑把容量为0也当做一种方法，这样可以递推得到其他结果。若dp[0]是0，递推结果将都是0）
4.遍历顺序：先遍历数字嵌套遍历背包，背包一定是要倒序遍历。

代码

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum=0;for(int num:nums)sum+=num;if((target+sum)%2==1||target+sum<0)return 0;int left=(target+sum)/2;int dp[]=new int[left+1];dp[0]=1;for(int i=0;i<nums.length;i++){for(int j=left;j>=nums[i];j--){dp[j]+=dp[j-nums[i]];}}return dp[left];}
}

☆☆☆☆☆leetcode 474.一和零

题目链接：leetcode 474.一和零

题目分析

此题可以视为一个装满0的容量为m、装满1的容量为n的背包，可以装多少个物品（也就是字符串），每个字符串的重量也就是字符串中0和1的数量，每个字符串的价值是1（加入个数即加一），相当于一个二维的背包。
1.dp数组含义：dp[i][j]表示最多有i个0和j个1的strs的最大子集的元素个数；
2.递推公式：dp[i][j]=Math.max(dp[i-x][j-y]+1,dp[i][j])；（其中x为当前字符串中0的个数，y为当前字符串中1的个数，x和y相当于物品的重量，物品的价值为1相当于计数）；
3.初始化：dp[0][0]=0；
4.遍历顺序：先遍历物品（字符串）嵌套遍历背包，背包一定是要倒序遍历。

代码

class Solution {public int findMaxForm(String[] strs, int m, int n) {int dp[][]=new int[m+1][n+1];for(String str:strs){int x=0,y=0;for(char s:str.toCharArray()){if(s=='0')x++;elsey++;}for(int i=m;i>=x;i--){for(int j=n;j>=y;j--)dp[i][j]=Math.max(dp[i-x][j-y]+1,dp[i][j]);}}return dp[m][n];}
}