leetcode416. 分割等和子集

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/partition-equal-subset-sum

題目描述

給你一個 只包含正整數(shù) 的 非空 數(shù)組 nums 。請你判斷是否可以將這個數(shù)組分割成兩個子集，使得兩個子集的元素和相等。

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

示例 2：
輸入：nums = [1,2,3,5]
輸出：false
解釋：數(shù)組不能分割成兩個元素和相等的子集。

提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100

暴力遞歸

動態(tài)規(guī)劃其實是對暴力遞歸的改寫,當(dāng)你對動態(tài)規(guī)劃沒有思路時,要先寫出暴力遞歸的嘗試,
這道題是典型的 0 -1 背包問題,就是要組成目標(biāo)和,那我們每到一個位置,都是面臨兩個選擇,選或者不選.分別對兩種情況進(jìn)行遞歸,最后比較兩種遞歸的情況就可以得到答案了.
還要注意找到base case ,我們代碼里注釋說明

代碼演示

    public boolean canPartition(int[] nums) {
        if(nums.length == 1){
            return false;
        }
        //計算數(shù)組累加和
       int sum = 0;
       for(int i = 0 ; i < nums.length;i++){
            sum += nums[i];
       }
       //如果不是偶數(shù)沒有辦法拆分成兩個數(shù)組和相等
         if(sum % 2 != 0){
             return false;
         }
         //能找到拆分方式的數(shù)量如果不等于0 ,就是可以拆分
         return process(nums,sum / 2,0) != 0;
     
    }

    /**
     * 暴力遞歸
     * 計算有多少種拆分方式
     * target 要組成的目標(biāo)數(shù)字
     * index 來到的下標(biāo)位置
     */
    public int process(int[]nums,int target,int index){
        //base case 如果來到越界位置,target == 0,前面選擇有效,返回1,代表一種有效方案
        if(index == nums.length){
            return target == 0 ? 1 : 0;
        }
        //target < 0 說明前面的選擇是無效的,返回 0
        if(target < 0){
            return 0;
        }
        // target == 0 ,前面選擇是合法的,返回1.
        if(target == 0){
            return 1;
        }
        //經(jīng)典背包解法,選和不選兩種情況 
        //不選時 去 index + 1 位置繼續(xù)做選擇
        int p1 = process(nums,target,index + 1);
        //選時 去 index + 1 位置繼續(xù)做選擇,需要組成的數(shù)字還剩target - nums[index]
        int p2 = process(nums,target - nums[index],index + 1);
        //返回最多的方法數(shù)
        return Math.max(p1,p2);

    }

動態(tài)規(guī)劃

解題思路

動態(tài)規(guī)劃是對暴力遞歸的改寫,三個步驟,
1.根據(jù)base case 初始化dp表
2.遞歸過程改成從dp 表種拿值得過程
3.返回遞歸調(diào)用得最初始狀態(tài),
具體這個問題種,位置如何依賴,如何拿值呢,我用圖演示下.
橫著得方向是target,豎得方向是index,(演示需要認(rèn)為數(shù)組長度是7,)
首先看,根據(jù)base case ,target == 0 時,返回1,所以dp 表種,target = 0 位置,全部初始化為1.
base case 里index 越界時,target = 0 時是1,其余是0,因為java語言本身數(shù)組初始化時,元素都是0,所以只需要初始化1出來就好了.
再看一般位置如何求解,以x位置為例.在遞歸中;
int p1 = process(nums,target,index + 1);
//選時 去 index + 1 位置繼續(xù)做選擇,需要組成的數(shù)字還剩target - nums[index]
int p2 = process(nums,target - nums[index],index + 1);
看到,x 依賴,index + 1 位置,正下方(i+ 1,target)的位置,和(target - nums[index],index + 1)這兩個位置以五角星位置參考,

  >  所以得出狀態(tài)轉(zhuǎn)移方程:
   dp[i][j] = Math.max(dp[i + 1][j] ,dp[i + 1][target - nums[index]]);

代碼演示

    /**
     * 動態(tài)規(guī)劃
     * @param nums
     * @return
     */
    public boolean dp(int[] nums){
        int sum = 0;
        for(int i = 0 ; i < nums.length;i++){
            sum += nums[i];
        }
        if(sum % 2 != 0){
            return false;
        }
        int N  = nums.length;
        int target = sum / 2;
        //動態(tài)規(guī)劃表
        int[][]dp = new int[N+1][target+ 1];
        //初始化 target == 0 時的位置為1.
        for (int i = 0; i <= N ; i++){
            dp[i][0] = 1;
        }
        for(int i = N - 1;i >= 0;i--){
            for (int j = 0; j <= target;j++){
                int p1 = dp[i + 1][j];
                int p2 = 0;
                //判斷位置不能越界
                if(j - nums[i] >= 0){
                    p2 = dp[i+1][j - nums[i] ];
                }
                //狀態(tài)轉(zhuǎn)移方程
                dp[i][j] = Math.max(p1,p2);
            }
        }

        return dp[0][target] != 0;

    }

動態(tài)規(guī)劃專題

leetcode.486. 預(yù)測贏家,動態(tài)規(guī)劃

leetcode354. 俄羅斯套娃信封問題

leetcode688. 騎士在棋盤上的概率

leetcode300. 最長遞增子序列

填滿背包的最大價格

-數(shù)字轉(zhuǎn)字符串,有多少種轉(zhuǎn)化結(jié)果文章來源地址http://www.zghlxwxcb.cn/news/detail-502525.html

到了這里，關(guān)于leetcode416. 分割等和子集(動態(tài)規(guī)劃-java)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！