华为公司网站建设方案模板,wordpress 5.0.3修改注册页,软件开发是什么意思,昌黎网站建设1049. 最后一块石头的重量 II
https://leetcode.cn/problems/last-stone-weight-ii/ 这个自己还是没想出来01背包对应。 本题其实就是尽量让石头分成重量相同的两堆#xff0c;相撞之后剩下的石头最小#xff0c;这样就化解成01背包问题了。 stones [2,7,4,1,8,1]也就是sum…1049. 最后一块石头的重量 II
https://leetcode.cn/problems/last-stone-weight-ii/ 这个自己还是没想出来01背包对应。 本题其实就是尽量让石头分成重量相同的两堆相撞之后剩下的石头最小这样就化解成01背包问题了。 stones [2,7,4,1,8,1]也就是sum232711114812差值为1。
class Solution {public int lastStoneWeightII(int[] stones) {int sum0;for(int i0;istones.length;i){sumstones[i];}int[] dpnew int[sum/21];for(int i0;istones.length;i){for(int jsum/2;jstones[i];j--){dp[j]Math.max(dp[j],dp[j-stones[i]]stones[i]);}}return sum-2*dp[sum/2];}
}494. 目标和
https://leetcode.cn/problems/target-sum/ 这个更难想到怎么和01背包问题结合了target是一个差值但±怎么判定呢。 x-(sum-x)target;——x(targetsum)/2; 这个真的好难理解啊
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];//如果target过大 sum将无法满足if ( target 0 sum -target) return 0;if ((target sum) % 2 ! 0) return 0;int size (target sum) / 2;if(size 0) size -size;int[] dp new int[size 1];dp[0] 1;for (int i 0; i nums.length; i) {for (int j size; j nums[i]; j--) {dp[j] dp[j - nums[i]];}}return dp[size];}
}474. 一和零
https://leetcode.cn/problems/ones-and-zeroes/ 这个也很难想到。 将m和n作为背包容量定义二维数组。
class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dpnew int[m1][n1];int x,y;for(str:strs){xy0;for(char ch : str.toCharArray()){if(ch0){x;}else{y;}}for (int i m; i x; i--) {for (int j n; j y; j--) {dp[i][j] Math.max(dp[i][j], dp[i - x][j - y] 1);}}}return dp[m][n];}
}
