2020-10-11 打卡題-動(dòng)態(tài)規(guī)劃
給定一個(gè)只包含正整數(shù)的非空數(shù)組互捌。是否可以將這個(gè)數(shù)組分割成兩個(gè)子集橱健，使得兩個(gè)子集的元素和相等浇揩。
注意:
每個(gè)數(shù)組中的元素不會(huì)超過(guò) 100
數(shù)組的大小不會(huì)超過(guò) 200示例 1:
輸入: [1, 5, 11, 5]
輸出: true
解釋: 數(shù)組可以分割成 [1, 5, 5] 和 [11].示例 2:
輸入: [1, 2, 3, 5]
輸出: false來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/partition-equal-subset-sum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有始藕。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)女淑，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處瞭郑。
-
動(dòng)態(tài)轉(zhuǎn)移方程：
狀態(tài)轉(zhuǎn)移方程 - 其中 dp[i][j] 表示從數(shù)組的 [0,i] 下標(biāo)范圍內(nèi)選取若干個(gè)正整數(shù)（可以是 0 個(gè)），是否存在一種選取方案使得被選取的正整數(shù)的和等于 j鸭你。初始時(shí)凰浮，dp 中的全部元素都是 false我抠。
- 題解：
public class CanPartition {
public boolean canPartition(int[] nums) {
// 數(shù)組長(zhǎng)度小于2，不能分成兩堆袜茧，直接返回False
if(nums.length < 2) return false;
int sum = 0,max_num=0;
// 計(jì)算數(shù)值總和、尋找最大數(shù)
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
max_num = Math.max(max_num, nums[i]);
}
// 總和不能平分瓣窄，即無(wú)法分成兩堆笛厦，直接返回False
if(sum%2 == 1) return false;
// 平均數(shù)小于最大數(shù)字，說(shuō)明包含負(fù)數(shù)俺夕，不符合題意裳凸，直接返回False
if(max_num > sum/2) return false;
// dp[i][j]: 在[0,i]范圍內(nèi)，nums數(shù)組能夠找到若干個(gè)數(shù)字加和結(jié)果為j
boolean dp[][] = new boolean[nums.length][sum/2+1];
dp[0][nums[0]] = true;
for (int i = 0; i < nums.length; i++) {
dp[i][0] = true;
}
for (int j = 1; j < sum / 2 + 1; j++) {
for (int i = 1; i < nums.length; i++) {
// 狀態(tài)轉(zhuǎn)移方程
if(j>=nums[i]) dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]];
else dp[i][j] = dp[i-1][j];
}
}
return dp[nums.length-1][sum/2];
}
public static void main(String args[]){
int nums[] = new int[]{1,2,3,6}; // true
int nums2[] = new int[]{1,2,3,6,6}; // true
int nums3[] = new int[]{1,2,3,5}; // false
int nums4[] = new int[]{100}; // false
System.out.println((new CanPartition()).canPartition(nums));
System.out.println((new CanPartition()).canPartition(nums2));
System.out.println((new CanPartition()).canPartition(nums3));
System.out.println((new CanPartition()).canPartition(nums4));
}
}
附：例子[1,2,3,6]劝贸，結(jié)果返回True
圖示
