目標(biāo)和（放滿背包的方法有幾種）

力扣題目鏈接(opens new window)

難度：中等

給定一個(gè)非負(fù)整數(shù)數(shù)組，a1, a2, ..., an, 和一個(gè)目標(biāo)數(shù)，S?，F(xiàn)在你有兩個(gè)符號(hào) + 和 -。對(duì)于數(shù)組中的任意一個(gè)整數(shù)，你都可以從 + 或 -中選擇一個(gè)符號(hào)添加在前面。

返回可以使最終數(shù)組和為目標(biāo)數(shù) S 的所有添加符號(hào)的方法數(shù)。

示例：

• 輸入：nums: [1, 1, 1, 1, 1], S: 3
• 輸出：5

解釋：

• -1+1+1+1+1 = 3
• +1-1+1+1+1 = 3
• +1+1-1+1+1 = 3
• +1+1+1-1+1 = 3
• +1+1+1+1-1 = 3

一共有5種方法讓最終目標(biāo)和為3。

提示：

• 數(shù)組非空，且長(zhǎng)度不會(huì)超過 20 。
• 初始的數(shù)組的和不會(huì)超過 1000 。
• 保證返回的最終結(jié)果能被 32 位整數(shù)存下。

思路

回顧一下 分割等和子集 和 最后一塊石頭II

前者是將集合分成兩個(gè)相等的子集，后者是將集合分成兩個(gè)盡可能相等的子集

共同點(diǎn)是什么？都是先把問題轉(zhuǎn)換成將當(dāng)前題目給的數(shù)組集合一分為二

因此，本題要往01背包問題上靠，也要先轉(zhuǎn)換為一個(gè)將集合劃分成兩部分的問題

怎么轉(zhuǎn)呢？

題目要在一個(gè)非負(fù)整數(shù)數(shù)組nums中的任意一個(gè)整數(shù)前加正負(fù)號(hào)，實(shí)現(xiàn)所有元素相加后等于目標(biāo)值target，最后統(tǒng)計(jì)一共有多少種相加的方法（即一共有多少種放正負(fù)號(hào)的方法）

那么我們就可以把數(shù)組元素分為兩個(gè)子集，一個(gè)子集中的元素前面都加正號(hào)，另一個(gè)子集則都加負(fù)號(hào)

這不就有兩個(gè)子集了嘛（md這正常人能想到？）

設(shè)加負(fù)號(hào)的子集為 negativeSign， 加正號(hào)的子集為 plusSign

注意，此時(shí)我們討論的兩個(gè)子集都是已經(jīng)通過dp劃分好的，里面不帶正負(fù)號(hào)

那么，兩個(gè)子集的元素相加應(yīng)該等于非負(fù)整數(shù)數(shù)組nums的元素之和sum

兩個(gè)子集的元素相減應(yīng)該等于目標(biāo)值target

抽象為公式如下：

① plusSign + negativeSign = sum；
② plusSign - negativeSign = target；

合并一下可以得到: plusSign = (sum + target) / 2;

在01背包問題中，只需用一個(gè)子集充當(dāng)背包即可，因此這里可以選擇 加正號(hào)的子集plusSign 作為背包

以示例 nums: [1, 1, 1, 1, 1], target: 3 來說

轉(zhuǎn)換為背包問題后，背包的容量為 (5+3)/2 = 4 ,所謂的"物品"就是nums數(shù)組中的元素

當(dāng)然，這里用除法就會(huì)涉及不能整除的情況

若不能整除，代表該數(shù)組nums找不到能夠組合成目標(biāo)值target的方法，直接return 0

此時(shí)，問題就轉(zhuǎn)換成了：使用非負(fù)整數(shù)數(shù)組nums中的元素裝滿背包有幾種方法？

（注意，本題要找的是有幾種裝滿背包的方法）

區(qū)分一下之前做的背包問題的目標(biāo)

? 單純的01背包問題：裝滿某個(gè)背包時(shí)，物品的最大價(jià)值；

? 分割等和子集：往背包放入物品后，背包的最大重量（換句話說就是能不能用物品把背包裝滿，能就return true）

? 最后一塊石頭：往背包裝物品，能裝下的最大價(jià)值（能裝多少裝多少）

五步走

1、確定dp數(shù)組含義

老規(guī)矩，先回顧一下經(jīng)典01背包問題的dp數(shù)組定義

dp[j]: 背包容量為j時(shí)，裝滿背包的最大價(jià)值為dp[j]

轉(zhuǎn)換一下，本題的dp數(shù)組含義可以定義如下：使用所給的所有物品，裝滿容量為j的背包有dp[j]種方法

2、確定遞推公式

怎么推導(dǎo)出dp[j]呢？

這里要通過"物品"的角度來想，例如，當(dāng)前如果有一個(gè)物品（nums中的一個(gè)元素）要放入背包，假設(shè)背包容量是5（與示例保持一致, nums元素為5個(gè)1）

那么這個(gè)物品一定會(huì)放入背包中，因此也一定會(huì)占用掉背包的一部分容量，占用掉的容量是 j - nums[i]

根據(jù)dp數(shù)組的含義，在有一個(gè)物品確定放入的情況下，dp[5]就會(huì)轉(zhuǎn)變?yōu)閐p[5 - 1]，也就是dp[4]

有點(diǎn)亂？那再用直接一點(diǎn)的話描述一下上面發(fā)生的事情：

? 1、最開始，背包容量是5，此時(shí)按dp數(shù)組的定義，裝滿該背包會(huì)有dp[5]種方法；（因?yàn)檫€有五個(gè)容量，你隨便怎么裝，所有的方法就表示為dp[5]）

? 2、當(dāng)已經(jīng)有一個(gè)"物品"確定放入容量為5的背包時(shí)，背包容量縮減為4（不管你開始沒開始往里面放，先給你預(yù)留了），還是按定義，此時(shí)裝滿該背包會(huì)有dp[5-nums[0]]種方法(即dp[5 - 1] = dp[4])

? 3、當(dāng)已經(jīng)有兩個(gè)"物品"確定放入容量為5的背包時(shí)，背包容量縮減為3（不管你開始沒開始往里面放，先給你預(yù)留了）

? 按定義，此時(shí)裝滿該背包會(huì)有dp[5-nums[0]-nums[1]]種方法(即dp[5-1-1] = dp[3])

后面的情況以此類推

注意，一定要結(jié)合dp數(shù)組的定義

這里的dp[某某]指的是在"某某"容量下放入物品時(shí)，所有方法的集合

簡(jiǎn)單概括一下，例如：dp[j]，j為5，

• 已經(jīng)有0個(gè)的話，有 dp[5]種方法 湊成 容量為5的背包。

• 已經(jīng)有一個(gè)1（nums[i]） 的話，有 dp[4]種方法 湊成 容量為5的背包。
• 已經(jīng)有一個(gè)2（nums[i]） 的話，有 dp[3]種方法 湊成 容量為5的背包。
• 已經(jīng)有一個(gè)3（nums[i]） 的話，有 dp[2]種方法 湊成 容量為5的背包
• 已經(jīng)有一個(gè)4（nums[i]） 的話，有 dp[1]種方法 湊成 容量為5的背包
• 已經(jīng)有一個(gè)5 （nums[i]）的話，有 dp[0]種方法 湊成 容量為5的背包

那湊整dp[5]有多少方法呢？（即dp[5]怎么求）

就把所有的 dp[j - nums[i]] 累加起來即可

也就是dp[5] = dp[4] + dp[3] + dp[2] + dp[1] + dp[0]

總結(jié)為遞推公式就是：

dp[j] += dp[j - nums[i]]

該遞推公式很重要，在用背包解決排列組合問題時(shí)還能用

3、初始化dp數(shù)組

一切結(jié)合dp數(shù)組的含義：裝滿容量為j的背包有dp[j]種方法

來看dp[0]的情況

dp[0]即被包容量為0時(shí)裝滿背包的方法數(shù)量，這里又可以細(xì)分為兩種情況：要裝的物品重量不為0和重量為0

如果物品重量不為0

那么實(shí)際上我們是無法將該物品裝入容量為0的背包中的，那么是不是就意味著在該種情況下，dp[0] = 0 了呢？

我認(rèn)為也不是，因?yàn)?strong>背包容量為0是一種特殊情況，此時(shí)不論你往不往里面放東西（或者放不放得進(jìn)），背包都已經(jīng)處于放滿狀態(tài)，因此

dp[0]應(yīng)該是默認(rèn)有一種方式裝滿的，那就是什么也不放

由上述分析可知，dp[0]應(yīng)該初始化為1，即dp[0] = 1;

如果物品重量為0

接著上面的分析，若背包中物品重量為0, 假設(shè)：[0,0,0,0,0], target = 0

那這些0就還是可以往背包里面放的(放不放都一樣)，并且不同的物品（重量為0）往背包放就算是一種不同的放法

因此，dp[0]就是這五個(gè)重量為0的物品不斷組合放入背包內(nèi)的組合方式的種類數(shù)量

大概有32種，于是dp[0] = 32

以上分析是建立在認(rèn)同dp[0]應(yīng)該初始化為1的情況下成立的（因?yàn)槠渌闆r都是基于的dp[0] = 1推導(dǎo)出來的）

說了這么多，無非就是像說明清楚dp[0]初始化為1的可行性，記住本題 dp[0] = 1 就行

4、確定遍歷順序

仍然遵循先遍歷物品（nums），后遍歷背包容量的順序，且背包容量的遍歷方向是倒序的

這里在邏輯上與之前涉及重量的問題不太一樣，下面手動(dòng)推導(dǎo)一遍

（輸入：nums: [1, 1, 1, 1, 1], target: 3）

如圖所示為遍歷過程

注意dp數(shù)組的含義，使用所給的所有物品，裝滿容量為j的背包有dp[j]種方法

這里有兩個(gè)關(guān)鍵點(diǎn)：1、需要使用所有的物品；2、裝滿

• 不論遍歷的過程如何，最終我們需要求的是把所有物品放入容量為j的背包的方法，因?yàn)楸闅v物品的過程是一個(gè)一個(gè)遍歷的，所以放入所有物品的方法種類也是由最開始的情況不斷累加到最后才能得到的
• 一定要能夠裝滿當(dāng)前容量才算是一種方法，比如在容量為4的情況下，目前遍歷到第一個(gè)物品（也就是只有一個(gè)物品），無論如何是放不滿4個(gè)容量的，因此就算能夠放入當(dāng)前的一個(gè)物品，也不能算一種方法

說一下"裝滿方法"是怎樣計(jì)算的

因?yàn)?strong>01背包問題中，每個(gè)物品只能使用一次，那么在當(dāng)前物品能夠裝滿當(dāng)前容量的前提下，使用相同物品以不同順序放入背包的方法應(yīng)該視作同一種方法

什么意思呢？就是說假設(shè)現(xiàn)在遍歷到了nums[2]，我們手頭上有3個(gè)物品，此時(shí)容量遍歷到2的話，理論上我們有以下放入的方式：

nums[0] nums[1] nums[2]
nums[0] nums[2] nums[1]
nums[1] nums[0] nums[2]
nums[1] nums[2] nums[0]
nums[2] nums[1] nums[0]
nums[2] nums[0] nums[1]

其中，有一半的放入方式重復(fù)使用了物品，因此是不計(jì)入方法種類

代碼

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        //計(jì)算數(shù)組元素之和
        int sum = 0;
        for(auto num : nums) sum += num;

        //判斷兩種無解的情況
        //1、所給的target已經(jīng)大于sum
        //2、(sum + target) / 2不能整除，即計(jì)算背包容量時(shí)不能整除
        if(abs(target) > sum) return 0;//取絕對(duì)值
        if((sum + target) % 2 != 0) return 0;

        //計(jì)算背包容量
        int bagSize = (sum + target) / 2;

        //定義dp數(shù)組
        vector<int> dp(bagSize + 1, 0);

        //初始化dp數(shù)組
        dp[0] = 1;

        //遍歷dp數(shù)組
        for(int i = 0; i < nums.size(); ++i){//遍歷物品num
            // 如果當(dāng)前背包容量小于物品重量，換一個(gè)物品繼續(xù)遍歷容量（所以第二層循環(huán)的條件是j >= nums[i]）
            // 每一個(gè)元素一定是不可重復(fù)放入，所以從大到小遍歷
            for(int j = bagSize; j >= nums[i]; --j){//遍歷背包容量
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }
};

零一和

力扣題目鏈接(opens new window)

給你一個(gè)二進(jìn)制字符串?dāng)?shù)組 strs 和兩個(gè)整數(shù) m 和 n 。

請(qǐng)你找出并返回 strs 的最大子集的大小，該子集中 最多 有 m 個(gè) 0 和 n 個(gè) 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

• 輸入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
• 輸出：4
• 解釋：最多有 5 個(gè) 0 和 3 個(gè) 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 其他滿足題意但較小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不滿足題意，因?yàn)樗?4 個(gè) 1 ，大于 n 的值 3 。

示例 2：

• 輸入：strs = ["10", "0", "1"], m = 1, n = 1
• 輸出：2
• 解釋：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] 僅由 '0' 和 '1' 組成
• 1 <= m, n <= 100

思路

這題有點(diǎn)繞的其實(shí)，剛上手的話很容易將m、n看成兩個(gè)容器

其實(shí)這樣想是錯(cuò)誤的，本題實(shí)質(zhì)上還是01背包問題，只不過這個(gè)背包有"兩個(gè)維度"

什么意思呢？我解釋一下

先來說題意吧，題目要求是：m代表字符串中0的個(gè)數(shù)，n代表字符串中1的個(gè)數(shù)

然后，題目規(guī)定一組m、n，要求從字符串?dāng)?shù)組strs中找到能夠滿足m、n的最大子集，并返回該子集的大小

拿示例1來看，strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3

最多有 5 個(gè) 0 和 3 個(gè) 1 的strs中的最大子集是 {"10（m=1,n=1）","0001（m=3,n=1）","1","0"}

該子集的大小是4，因此結(jié)果值返回的是4

看出來了嗎？其實(shí)題目規(guī)定的"m = 5, n = 3"就是在設(shè)置背包的容量

確定了背包就好辦了，下面就套五部曲解決問題

五步走

1、確定dp數(shù)組的含義

注意，這里題目是要求最大子集個(gè)數(shù)，也就是背包中物品的個(gè)數(shù)

那么dp數(shù)組可以定義如下

dp[i][j]: 在背包"容量"(這里的容量指的是strs中一個(gè)子字符串中0、1的個(gè)數(shù))為i、j時(shí)能夠裝下物品的最大個(gè)數(shù)

雖然這里需要把dp數(shù)組設(shè)置成二維的，但其實(shí)本質(zhì)上和之前的一維01背包問題沒有區(qū)別

如果不好理解的話還是可以把dp數(shù)組看成是個(gè)一維的，例如dp[G],G是背包的容量，只不過G由兩個(gè)部分組成，一部分是i，一部分是j

（這里也可以把G想象成strs中一個(gè)子字符串，例如"10"）

2、確定遞推公式

因?yàn)楸绢}只是給放入背包的物品多增加了一個(gè)維度，所以遞推公式可以參考標(biāo)準(zhǔn)01背包問題的遞推公式（一維）

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

那么對(duì)照著本題的遞推公式就是

dp[i][j] = max(dp[i][j], dp[i - zeroNums][j - oneNums] + 1(物品數(shù)量));

解釋一下，

當(dāng)我們確定放入一個(gè)新的子字符串（假設(shè)是"10"），那么此時(shí)背包容量（i、j）就要對(duì)應(yīng)減少子字符串中0的個(gè)數(shù)（zeroNums）、子字符串中1的個(gè)數(shù)（oneNums），(zeroNums, oneNums)即為該子字符串（物品）的重量

當(dāng)然，此時(shí)包內(nèi)的物品數(shù)量要加1（類比之前的遞推公式，背包總價(jià)增加）

推導(dǎo)dp[i][j]時(shí)，有兩種情況：放東西和不放東西

這兩者取能夠使物品個(gè)數(shù)最大的那種情況就行，即上面的遞推公式

3、初始化dp數(shù)組

dp[0][0]時(shí)要初始化為0，即容量為(0,0)時(shí)，一個(gè)也裝不下

然后其余的部分也要初始化為0，為了防止遞推值被初始值覆蓋（詳見）

4、確定遍歷順序

和普通的01背包的一維解法一樣，這里也是先遍歷物品（子字符串），然后倒序遍歷背包容量(i,j)（對(duì)應(yīng)(zeroNums, oneNums)）

核心代碼如下，結(jié)合上面的圖來解釋

for (string str : strs) { // 遍歷物品，即子字符串，例如"10"
    int oneNum = 0, zeroNum = 0;
    for (char c : str) {//統(tǒng)計(jì)字符串中0、1的數(shù)量
        if (c == '0') zeroNum++;
        else oneNum++;
    }//以下是遍歷背包容量(i,j)
    //如果當(dāng)前背包容量(i,j)小于物品重量(zeroNum,oneNum),換一個(gè)物品（子字符串）再放入
    for (int i = m; i >= zeroNum; i--) { // 遍歷背包容量且從后向前遍歷！
        for (int j = n; j >= oneNum; j--) {
            dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
        }
    }
}

對(duì)應(yīng)到圖中就是，我們第一輪遍歷是從最下面的一行開始的，從右往左倒序遍歷

根據(jù)遞推公式有：dp[3][3] = max(dp[3][3], dp[3 - 1][3 - 1] + 1);（此時(shí)子字符串是"10"）

因?yàn)?code>dp[3][3]的初始值為0，所以dp[2][2]+1肯定要大一些，故dp[3][3] = dp[3 - 1][3 - 1] + 1;

那dp[2][2]又是多少？還是用遞推公式去算，得到dp[2][2] = max(dp[2][2], dp[2 - 1][2 - 1] + 1);，取決于dp[1][1]

同理，dp[1][1] = max(dp[1][1], dp[1 - 1][1 - 1] + 1);，最后可以算出dp[1][1]=dp[0][0]+1=1

所以，

dp[2][2]=1+1=2

dp[3][3]=2+1=3

此時(shí)可以得到圖中dp[3][3]處的遞推值，同理可以把整個(gè)dp數(shù)組的遞推值計(jì)算出來，結(jié)果如上圖所示

代碼

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        //定義dp數(shù)組,并初始化
        //二維數(shù)組，行列分別是0、1（可以顛倒）
        vector<vector<int>> dp(m + 1, vector(n + 1, 0));

        //遍歷dp數(shù)組
        for(string str : strs){//遍歷物品（子字符串）
            int zeroNums = 0, oneNums = 0;
            //統(tǒng)計(jì)字符串中的01個(gè)數(shù)
            for(char c : str){
                if(c == '0'){
                    zeroNums++;
                }else oneNums++;
            }
            for(int i = m; i >= zeroNums; --i){//遍歷背包容量(i,j),倒序
                for(int j = n; j >= oneNums; --j){//i\j遍歷順序可以更換，因?yàn)楸举|(zhì)上還是容量
                    dp[i][j] = max(dp[i][j], dp[i - zeroNums][j - oneNums] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

二刷理解

本題實(shí)質(zhì)上還是一個(gè)壓縮的01背包問題

 		for(string str : strs){//遍歷物品
            ...
            //以下兩層for循環(huán)用于遍歷背包容量
            for(int i = m; i >= zeroNum; --i){
                for(int j = n; j >= oneNum; --j){
                    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }

前進(jìn)或后退

一個(gè)數(shù)組[0,1,2,3,4,5,6,7,8,9]，從0出發(fā)，每次可以前進(jìn)一步或者后退一步，問走n步，回到0的情況有多少種。

本題使用動(dòng)態(tài)規(guī)劃如何解決

思路

本題實(shí)際上是非?；A(chǔ)的dp題，按五部曲來分析即可

1、確定dp數(shù)組的含義

這里就直接使用一維dp數(shù)組了。dp[i]：走i步回到0的情況有dp[i]種

2、確定遞推公式

該問題中只有兩種狀態(tài)，要么向前走（遠(yuǎn)離0），要么向后走（走向0）

即分別對(duì)應(yīng)：dp[i] += dp[i + 1] 和 dp[i] += dp[i - 1]

使用二維dp數(shù)組就是dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];

為什么是累加？詳見目標(biāo)和與零錢兌換II

以往后走為例。簡(jiǎn)單來說，回到0位置有dp[i]種情況，往后走一步到達(dá)i - 1位置，此處到0位置有dp[i - 1]種情況，再往后走到i - 2也同理。于是到0位置的所有情況需要分別把i - 1、i - 2、i - 3...0的所有情況加起來，也就是累加咯

此外，因?yàn)橹挥?0個(gè)格子，所以我們需要注意處理邊界條件

• 當(dāng)i=0時(shí)，只能向后走一步，即dp[i] += dp[1]。
• 當(dāng)i=9時(shí)，只能向前走一步，即dp[i] += dp[8]。

3、初始化dp數(shù)組

dp[0] = 1，表示在前0步之后，到達(dá)位置0的走法總數(shù)為1。

4、確定遍歷順序

累加，從前往后文章來源地址http://www.zghlxwxcb.cn/news/detail-417228.html

代碼

#include <vector>

using namespace std;

int countWays(int n) {
    vector<int> dp(10, 0);
    dp[0] = 1;

    for (int i = 1; i <= n; ++i) {
        vector<int> temp(10, 0);
        for (int j = 0; j < 10; ++j) {
            if (j == 0) {
                temp[j] = dp[1];
            } else if (j == 9) {
                temp[j] = dp[8];
            } else {
                temp[j] = dp[j - 1] + dp[j + 1];
            }
        }
        dp = temp;
    }

    return dp[0];
}

int main() {
    int n = 10; // 假設(shè)要走10步
    int result = countWays(n);
    cout << result << endl; // 輸出結(jié)果
    return 0;
}

到了這里，關(guān)于【LeetCode動(dòng)態(tài)規(guī)劃#07】01背包問題一維寫法（狀態(tài)壓縮）實(shí)戰(zhàn)，其二（目標(biāo)和、零一和）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！