更换网站空间,建设工程规划许可证网站,扁平化设计 科技感网站素材,上海做网站的知名企业题目来源#xff1a; leetcode题目#xff0c;网址#xff1a;LCR 101. 分割等和子集 - 力扣#xff08;LeetCode#xff09;
解题思路#xff1a; 将数组分为等和的两部分等价于数组是否中存在部分元素和为数组总和的一半。 首先#xff0c;若数组长度为 1 或数组…题目来源 leetcode题目网址LCR 101. 分割等和子集 - 力扣LeetCode
解题思路 将数组分为等和的两部分等价于数组是否中存在部分元素和为数组总和的一半。 首先若数组长度为 1 或数组总和为奇数肯定不存在部分元素和为数组总和的一半。 接着对数组进行动态规划其中 dp[i][j] 表示前 i 个元素是否能使部分元素和为 j 递推关系为 dp[i][j]dp[i-1][j] || dp[i-1][j-nums[i]]。 最后返回结果即可。
解题代码
class Solution {public boolean canPartition(int[] nums) {int sumArrays.stream(nums).sum();if(nums.length1 || sum%2!0){return false;}int targetsum/2;boolean[][] dpnew boolean[nums.length][target1];//dp[i][j] 0-i 范围内是否能通过求和得到 jfor(int i0;idp.length;i){dp[i][0]true;}for(int i1;idp.length;i){for(int j0;jdp[0].length;j){dp[i][j]dp[i-1][j];if(!dp[i][j] j-nums[i]0){dp[i][j]dp[i-1][j-nums[i]];}}if(dp[i][target]){return true;}}return dp[nums.length-1][target];}
}
总结 没做出来看官方题解的。 这题是简单题但是主站中与本题相同的题是中等题搞不懂。
