2020-10-11 打卡題-動(dòng)態(tài)規(guī)劃

給定一個(gè)只包含正整數(shù)的非空數(shù)組。是否可以將這個(gè)數(shù)組分割成兩個(gè)子集，使得兩個(gè)子集的元素和相等。
注意:
每個(gè)數(shù)組中的元素不會(huì)超過 100
數(shù)組的大小不會(huì)超過 200

示例 1:
輸入: [1, 5, 11, 5]
輸出: true
解釋: 數(shù)組可以分割成 [1, 5, 5] 和 [11].

示例 2:
輸入: [1, 2, 3, 5]
輸出: false

來源：力扣（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]);
        }
        // 總和不能平分，即無法分成兩堆，直接返回False
        if(sum%2 == 1) return false;
        // 平均數(shù)小于最大數(shù)字，說明包含負(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

圖示