/** <p>给你一个 <strong>只包含正整数 </strong>的 <strong>非空 </strong>数组 <code>nums</code> 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。</p> <p> </p> <p><strong>示例 1:</strong></p> <pre> <strong>输入:</strong>nums = [1,5,11,5] <strong>输出:</strong>true <strong>解释:</strong>数组可以分割成 [1, 5, 5] 和 [11] 。</pre> <p><strong>示例 2:</strong></p> <pre> <strong>输入:</strong>nums = [1,2,3,5] <strong>输出:</strong>false <strong>解释:</strong>数组不能分割成两个元素和相等的子集。 </pre> <p> </p> <p><strong>提示:</strong></p> <ul> <li><code>1 <= nums.length <= 200</code></li> <li><code>1 <= nums[i] <= 100</code></li> </ul> <div><div>Related Topics</div><div><li>数组</li><li>动态规划</li></div></div><br><div><li>👍 1376</li><li>👎 0</li></div> */ //leetcode submit region begin(Prohibit modification and deletion) class Solution { public boolean canPartition(int[] nums) { if(nums.length==0){ return false; } int total =0; for (int i = 0; i < nums.length; i++) { total+=nums[i]; } if(total%2!=0){ return false; } int amount = total/2; int n = nums.length; boolean[][] dp = new boolean[n+1][amount+1]; for (int i = 0; i <=n ; i++) { dp[i][0]=true; } for (int i = 1; i <= n; i++) { for (int j = 1; j <=amount ; j++) { if(j-nums[i-1]>=0){ //由于是boolean 所以用或运算 dp[i][j]=dp[i-1][j] || dp[i-1][j-nums[i-1]]; }else{ dp[i][j]=dp[i-1][j]; } } } return dp[n][amount]; } } //leetcode submit region end(Prohibit modification and deletion)
不恋尘世浮华,不写红尘纷扰