龙岗区网站建设公司,学做简单网站,加工平台制作,网站建设公司提成力扣爆刷第74天–动态规划 文章目录 力扣爆刷第74天--动态规划一、494.目标和二、474.一和零 一、494.目标和
题目链接#xff1a;https://leetcode.cn/problems/target-sum/description/ 思路#xff1a;求目标和的组合数#xff0c;把物品里的元素分为左右两堆#xff0…力扣爆刷第74天–动态规划 文章目录 力扣爆刷第74天--动态规划一、494.目标和二、474.一和零 一、494.目标和
题目链接https://leetcode.cn/problems/target-sum/description/ 思路求目标和的组合数把物品里的元素分为左右两堆leftrightsumleft-righttarget两式相加可以得到left (sum target)/2那么题目就转变成了从物品中挑选元素把容量为left的背包填满有多少种元素组合这求的是组合数定义dp[j]表示把容量为j的背包填满有dp[j]种方法。每一个元素可以选择加入也可以选择不加入不加入nums[i]有dp[j]种方法填满j容量加入nums[i]有dp[j-nums[i]]种方法填满j容量故递推公式为dp[j] dp[j-nums[i]]。
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum 0;for(int i 0; i nums.length; i) {sum nums[i];}if(sum Math.abs(target)) return 0;if((sum target) % 2! 0) return 0;int left Math.abs((sum target) / 2);int[] dp new int[left1];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];}
}二、474.一和零
题目链接https://leetcode.cn/problems/ones-and-zeroes/description/ 思路一和零求符合m个0和n个1的元素的个数其实就是背包可放入元素的最大数量背包有两个维度而已是二重背包和0,1背包的做法是一样的。
class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp new int[m1][n1];for(String str: strs) {int a 0, b 0;for(char c: str.toCharArray()) {if(c 0) a;else b;}for(int i m; i a; i--) {for(int j n; j b; j--) {dp[i][j] Math.max(dp[i][j], dp[i-a][j-b] 1);}}}return dp[m][n];}
}
