摘要

• 用動(dòng)態(tài)規(guī)劃解決問(wèn)題時(shí)，不僅要從簡(jiǎn)單的子問(wèn)題來(lái)考慮遞推公式，也要從問(wèn)題的整體來(lái)考慮，看問(wèn)題的輸入?yún)?shù)本身有什么性質(zhì)和公式，也有助于得到遞推公式。

LeetCode1049 最后一塊石頭的重量 II

1049. 最后一塊石頭的重量 II - 力扣（Leetcode）

• 從問(wèn)題的整體來(lái)考慮，要使一堆石頭兩兩一起“粉碎”后剩余的重量值最小，那么應(yīng)該把這堆石頭盡可能地分成重量相等或相近的兩堆石頭，分出來(lái)的兩堆石頭兩兩一起“粉碎”后剩余的重量值就是最小的重量值。注意，如果粉碎后的石頭有剩余，那可以看作繼續(xù)分成重量盡可能相近的兩堆，然后繼續(xù)讓這兩堆石頭兩兩一起粉碎。
• 將一堆石頭分成兩堆重量盡可能相近的石頭，設(shè)石頭的重量總和為sum
  • 對(duì)于石頭i，要么在第一堆里，要么在第二堆里。只針對(duì)分出來(lái)的第一堆石頭，石頭i要么在第一堆里，要么不在，這和 0-1 背包問(wèn)題對(duì)于物品的取法是一致的。
  • 兩堆石頭的重量要盡可能相近，所以分出來(lái)的一堆石頭的重量最大值應(yīng)該是sum / 2 + sum % 2。
• 那么，問(wèn)題可以轉(zhuǎn)化成：“從一堆石頭中任取石頭，每個(gè)石頭要么不取，要么取一次，得到的重量值盡可能地接近sum / 2 + sum % 2”?！拔锲贰笔鞘^，“背包”是一堆石頭，“背包”的最大容量是sum / 2 + sum % 2，“物品”的價(jià)值是stones[i]，“物品”的重量也是stones[i]。設(shè)half為sum / 2 + sum % 2。
• dp數(shù)組及下標(biāo)的含義：dp[j]表示的是，任取石頭，得到的重量值不超過(guò)j的最大值，設(shè)dp[j]的更新次數(shù)為i，則dp[j]對(duì)應(yīng)的可選的石頭下標(biāo)范圍為0到i。
• 計(jì)算完dp數(shù)組后，按上述規(guī)則取石頭后第一堆的重量為dp[half]，第二堆的重量為sum - dp[half]，則粉碎后剩余的重量為abs(sum - dp[half] - dp[half])。

題解代碼如下

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        if (stones.empty()) return 0;
        if (stones.size() == 1) return stones.back();
        
        int sum = 0;
        for (auto& iter : stones) sum += iter;
        int half = sum / 2  + sum % 2;
        vector<int> dp(half + 1, 0);

        for (int i = 0; i < stones.size(); i++) {
            for (int j = half; j >= stones[i]; j--) {
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }

        return abs(sum - dp[half] - dp[half]);
    }
};

LeetCode494 目標(biāo)和

494. 目標(biāo)和 - 力扣（Leetcode）

• 這道題目，從整體來(lái)看，“構(gòu)造表達(dá)式”也可以看作將輸入的參數(shù)分為兩部分：一部分添加+號(hào)，作為被減數(shù)；另一部分添加-號(hào)，作為減數(shù)。設(shè)nums中各個(gè)整數(shù)的和為sum。設(shè)被減數(shù)為minuend（正數(shù)），減數(shù)為subtractor（正數(shù)），則兩者的和為sum，兩者的差為target。

• 通過(guò)以上推導(dǎo)，可以看出minuend的取法，即從nums中任取k個(gè)元素，使得選取的元素的和盡可能接近(sum+target)/2，當(dāng)選取的元素的和恰好等于(sum+target)/2時(shí)，說(shuō)明找到了一種使得構(gòu)造的表達(dá)式的結(jié)果等于target的方案。

• 確定dp數(shù)組及下標(biāo)的含義：dp[j]為從nums中任取整數(shù)，選取的整數(shù)的和恰好為j的情況，dp[j]的更新次數(shù)對(duì)應(yīng)可以選取的nums的下標(biāo)范圍，設(shè)dp[j]更新了i次，dp[j]對(duì)應(yīng)的可選取的nums的下標(biāo)范圍是0到i。

• 要注意的是，這道題目的dp數(shù)組的含義和之前的題目不同。

  • LeetCode1049 最后一塊石頭的重量、LeetCode416 分割等和子集，這兩道題我們并不關(guān)心有多少種組合方式得到目標(biāo)值，我們關(guān)心的是是否能得到目標(biāo)值，或得到一個(gè)接近目標(biāo)值的值。用 0-1 背包的語(yǔ)言來(lái)描述，就是想讓背包盡可能地裝滿，或者裝入的物品價(jià)值盡可能大。
  • 但 LeetCode494 目標(biāo)和，除了要關(guān)心是否能得到目標(biāo)值，還要知道有多少種方法得到目標(biāo)值。用 0-1 背包的語(yǔ)言來(lái)描述，就是有多少種方法恰好能裝滿背包。此時(shí)再用描述背包裝入的重量或價(jià)值的dp來(lái)解決題目就不合適了，dp數(shù)組應(yīng)該描述的是有多少種方式能恰好裝滿容量為j的背包。

• 確定遞推公式，先看簡(jiǎn)單的子問(wèn)題

  • 一個(gè)元素都沒(méi)有選取，選取出的minuend是空集，空集只有一種，且和為0，所以dp[0]初始化為1，此時(shí)minuend中整數(shù)的和只能是0，所以當(dāng)j > 0時(shí)，dp[j]初始化為0。
  • nums[0]是第一個(gè)嘗試選取的元素，如果選nums[0]，則當(dāng)j == nums[0]時(shí)，dp[j]的值為1，說(shuō)明得到和為nums[0]有一種方式，就是選取nums[0]。
  • 假設(shè)已經(jīng)在nums[0]到nums[i-1]中選取了k個(gè)數(shù)，再選取了一個(gè)整數(shù)nums[i]。那么為了使得當(dāng)前選取方式的minuend中的整數(shù)的和為j，就要再?gòu)?code>nums[0]到nums[i-1]選出一個(gè)和為j - nums[i]的集合。根據(jù)dp數(shù)組的定義，從nums[0]到nums[i-1]選出一個(gè)和為j - nums[i]的集合的種數(shù)就是dp[j - nums[i]]。
  • 這樣就可以得到遞推公式，其中i為dp[j]的更新次數(shù)下標(biāo)（從0開始），i=-1表示初始狀態(tài)

• 初始狀態(tài)已經(jīng)在遞推公式中寫明，即dp[0]初始化為1，其他dp[j]初始化為0。

• 以nums={1, 1, 1, 1, 1}; target=3為例，根據(jù)，求得minuend=4，要注意的是，有兩種情況是可以直接知道答案的種數(shù)是0的：

  1. sum的絕對(duì)值小于target的絕對(duì)值，即 abs(sum) < abs(target)，此時(shí)說(shuō)明nums中的元素全取+或全取-都不可能得到值為target的和。
  2. sum + target不能被2整除，因?yàn)?code>nums中都是整數(shù)，對(duì)于minuend的定義是從nums中取出的部分整數(shù)的和，所以minuend也應(yīng)該是整數(shù)，如果sum + target不能被2整除，說(shuō)明不存在minuend使得構(gòu)造出的表達(dá)式的結(jié)果為target。

• 首先畫出其二維dp數(shù)組，初始狀態(tài)保存在i=-1那一行，對(duì)應(yīng)沒(méi)有從nums中選取任何整數(shù)

• 確定dp[j]的遍歷順序，即更新順序，由遞推公式 ，可以知道dp[j]的更新依賴的是上一行的且在其左邊的值，所以更新順序應(yīng)該是j從大到小，即從左到右。
• 所以先滑動(dòng)dp[4]，dp[4]=dp[4]+dp[4-1]=0;

• dp[2]和dp[3]同理

• 再看dp[1]，nums[0]==1，dp[1]=dp[1]+dp[1-1]=1。

• 最后看dp[0]，如果j - nums[i] > 0，則dp[0]還是1，因?yàn)闆](méi)有出現(xiàn)空集以外的集合內(nèi)元素和等于0的情況。

• 重復(fù)滑動(dòng)一行的過(guò)程，把dp數(shù)組填完

• 最后的dp[minuend]就是使得構(gòu)造出的表達(dá)式的結(jié)果等于target的方法數(shù)。

題解代碼如下

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (auto& iter : nums) sum += iter;
        // 直接求得方法數(shù)為 0 的情況
        if ((sum + target) % 2) return 0;
        if (abs(sum) < abs(target)) return 0;
        // 初始化 dp 數(shù)組
        int minuend = (sum + target) / 2;
        vector<int> dp(minuend + 1, 0);
        dp[0] = 1;
        // 從 i=0 開始，逐行更新 dp 數(shù)組
        for (int i = 0; i < nums.size(); i++) {
            for (int j = minuend; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[minuend];
    }
};

LeetCode474 一和零

474. 一和零 - 力扣（Leetcode）

• 這道題目也是 0-1 背包問(wèn)題，“物品”是集合中的元素，“背包”是子集。不過(guò)“物品”的“重量”變成了兩個(gè)維度：一是“0”的個(gè)數(shù)，二是“1”的個(gè)數(shù)。題目要求子集中的元素個(gè)數(shù)最多，所以每個(gè)元素的“價(jià)值”是相等的，可以都設(shè)為1。

• 確定dp數(shù)組及數(shù)組下標(biāo)的含義：dp[j][k]的含義是，從strs中任取字符串，這些字符串包含的 '0' 不超過(guò) j 個(gè)，包含的 ’1‘ 不超過(guò) k 個(gè)。對(duì)每個(gè)物品，dp[j][k]的值都會(huì)進(jìn)行一次更新，所以依然可以省略遍歷到第i個(gè)物品這個(gè)維度。

• 遞推公式，可以看出只是“重量”多了一個(gè)維度，dp[i][j][k]還是由兩種可能推出：一是不放入物品i，二是放入物品i
  

• 初始化過(guò)程隱含在dp數(shù)組的計(jì)算過(guò)程中，先將dp數(shù)組全部初始化成0。

• 同樣要注意dp[j][k]的更新依賴于dp[j - numsOf0[i]][k - numsOf1[i]]，所以j應(yīng)從大到小，k也應(yīng)該從大到小。

題解代碼如下

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<int> numsOf0(strs.size(), 0);
        vector<int> numsOf1(strs.size(), 0);
        for (int i = 0; i < strs.size(); i++) {
            for (auto& ch : strs[i]) {
                numsOf0[i] += ch == '0';
                numsOf1[i] += ch == '1';
            }
        }

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        
        for (int i = 0; i < strs.size(); i++) {
            for (int j = m; j >= numsOf0[i]; j--) {
                for (int k = n; k >= numsOf1[i]; k--) {
                    dp[j][k] = max(dp[j][k], dp[j - numsOf0[i]][k - numsOf1[i]] + 1);
                }
            }
        }

        return dp[m][n];
    }
};