国外免费网站域名服务器入口,君通网站怎么样,百度云自助建站,门户网站对应序号是什么0-1背包模版
有n个物品#xff0c;它们有各自的体积和价值#xff0c;现有给定容量的背包#xff0c;如何让背包里装入的物品具有最大的价值总和#xff1f; 当前操作#xff1f;枚举第i个物品选还是不选#xff0c;不选容量不变#xff0c;选容量减少 子问题#xff…0-1背包模版
有n个物品它们有各自的体积和价值现有给定容量的背包如何让背包里装入的物品具有最大的价值总和 当前操作枚举第i个物品选还是不选不选容量不变选容量减少 子问题从前i个物品中的最大容量和 下一个子问题不选剩余容量为c前i-1个物品中的最大容量和选 剩余容量为c-w[i]前i个物品中的最大容量和
public int dfs(int i, int c) {if (i 0) {return 0;}if (c w[i]) {return dfs(i - 1, c);}return dfs(n - 1, capacity);}题目
目标和 给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘’ 或 ‘-’ 然后串联起所有整数可以构造一个 表达式
例如nums [2, 1] 可以在 2 之前添加 ‘’ 在 1 之前添加 ‘-’ 然后串联起来得到表达式 “2-1” 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1
输入nums [1,1,1,1,1], target 3 输出5 解释一共有 5 种方法让最终目标和为 3 。 -1 1 1 1 1 3 1 - 1 1 1 1 3 1 1 - 1 1 1 3 1 1 1 - 1 1 3 1 1 1 1 - 1 3 示例 2
输入nums [1], target 1 输出1
提示
1 nums.length 20 0 nums[i] 1000 0 sum(nums[i]) 1000 -1000 target 1000
题解
记忆化搜索
class Solution {private int[] nums;private int[][] cache;public int findTargetSumWays(int[] nums, int target) {// p 正数的和// s nums的和// target p - (s - p)// p (s t)/2//题目转化为从nums选择数使他们恰好等于(s t)/2// 其中(st)必须为偶数for (int x : nums) {target x;}if (target 0 || target % 2 1) {return 0;}target / 2;this.nums nums;int n nums.length;cache new int[n][target 1];for (int i 0; i n ; i) {Arrays.fill(cache[i],-1);}return dfs(n - 1,target);}public int dfs(int i, int c) {if (i 0) {return c 0 ? 1 : 0;}if (cache[i][c] ! -1) {return cache[i][c];}if (c nums[i]) {return cache[i][c] dfs(i - 1, c);}return cache[i][c] dfs(i - 1, c) dfs(i - 1, c - nums[i]);}
}递推
class Solution {public int findTargetSumWays(int[] nums, int target) {for (int x : nums) {target x;}if (target 0 || target % 2 1) {return 0;}target / 2;int n nums.length;int[][] f new int[n1][target1];f[0][0] 1;for (int i 0; i n; i) {for (int c 0; c target; c) {if (c nums[i]) {f[i1][c] f[i][c];} else {f[i1][c] f[i][c] f[i][c-nums[i]];}}}return f[n][target];}
}空间优化两个数组
class Solution {public int findTargetSumWays(int[] nums, int target) {for (int x : nums) {target x;}if (target 0 || target % 2 1) {return 0;}target / 2;int n nums.length;int[][] f new int[2][target1];f[0][0] 1;for (int i 0; i n; i) {for (int c 0; c target; c) {if (c nums[i]) {f[(i1)%2][c] f[i%2][c];} else {f[(i1)%2][c] f[i%2][c] f[i%2][c-nums[i]];}}}return f[n%2][target];}
}空间优化一个数组
class Solution {public int findTargetSumWays(int[] nums, int target) {for (int x : nums) {target x;}if (target 0 || target % 2 1) {return 0;}target / 2;int n nums.length;int[] f new int[target1];f[0] 1;for (int x : nums) {for (int c target; c x; c--) {f[c] f[c-x];}}return f[target];}
}
