非常好的學(xué)習(xí)資料

題目

鏈接

給定一個(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ì)超過(guò) 20 。 初始的數(shù)組的和不會(huì)超過(guò) 1000 。 保證返回的最終結(jié)果能被 32 位整數(shù)存下。

關(guān)鍵詞

回溯，帶備忘錄的回溯，動(dòng)態(tài)規(guī)劃，背包問(wèn)題

解題

回溯

看這題，第一反應(yīng)就是回溯。

回溯有個(gè)基本框架

int backtrace(vector<int> nums, 選擇路徑){
    if (滿足退出條件)
        return result;

    for (auto 選擇: 選擇列表){
        做選擇
        backtrace(nums, 選擇路徑);
        撤銷選擇
    }
}

寫個(gè)基礎(chǔ)回溯應(yīng)該問(wèn)題不大

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        return backtrack(nums, 0, (long)S, 0);
    }

    int backtrack(vector<int> &nums, int i, long res, int result){
        if (i == nums.size()){
            if (res == 0)
                result += 1;
            return result;
        }
        result = backtrack(nums, i+1, res+nums[i], result);
        result = backtrack(nums, i+1, res-nums[i], result);
        return result;
    }
};

帶備忘錄的回溯

這個(gè)問(wèn)題一定有重復(fù)子問(wèn)題，那我把子問(wèn)題的答案記錄下來(lái)。這個(gè)解法要稍微設(shè)計(jì)一下，怎么記錄子問(wèn)題。

比較好的方法是用map，信息應(yīng)該包含：對(duì)第i個(gè)數(shù)做選擇，剩下來(lái)的數(shù)需要湊出來(lái)的數(shù)值res，有幾種湊法。相當(dāng)于要記三個(gè)信息，有點(diǎn)頭大！

好消息是 一旦確定 i 和 res，就能獲得方案數(shù)！即map為string和int的映射表，string包含i和res信息即可。

class Solution {
public:
    unordered_map<string, int> memo;

    int findTargetSumWays(vector<int>& nums, int S) {
        return backtrack(nums, 0, (long)S);
    }

    int backtrack(vector<int> &nums, int i, long res){
        if (i == nums.size()){
            if (res == 0)
                return 1; //這里需要換，返回的是已明確的方案數(shù)
            return 0;
        }
        string key = to_string(i) + '_' + to_string(res); //這里要想一下
        if (memo.find(key) != memo.end())
            return memo[key];

        //result應(yīng)是所有方案的和
                int result = backtrack(nums, i+1, res+nums[i]) + backtrack(nums, i+1, res-nums[i]);
        memo[key] = result;
        return result;
    }
};

背包&動(dòng)態(tài)規(guī)劃

我的數(shù)學(xué)思維能力需要專項(xiàng)訓(xùn)練的樣子，目前還不行

A: 所有采用+的數(shù)的集合，B：所有采用-的數(shù)的集合

sum(A) - sum(B) = S

sum(A) + sum(A) = S + sum(B) + sum(A)

sum(A) = (S + sum)/2

小可愛(ài)發(fā)現(xiàn)什么了！沒(méi)有錯(cuò)，問(wèn)題變成了 從整體集合中挑選數(shù)，使它們的和為一個(gè)常數(shù)，有多少種方案。

典型的背包問(wèn)題了，用動(dòng)態(tài)規(guī)劃來(lái)解。

動(dòng)態(tài)規(guī)劃三步走：確定定義，寫狀態(tài)轉(zhuǎn)移函數(shù)，寫base case。

• 確定定義

  dp[i][j]：前i個(gè)數(shù)中任意挑選，和為j的有多少種方案

• 狀態(tài)轉(zhuǎn)移：

  dp[i][j] = dp[i-1][j] (不放第i個(gè)數(shù)的方案數(shù)）+ dp[i-1][j-第i個(gè)數(shù)]（放第i個(gè)數(shù)的方案數(shù)）

• base case：

  dp[:][0] = 1

寫代碼的時(shí)候有個(gè)問(wèn)題

我的i表示前i個(gè)數(shù)里挑選，i=0的時(shí)候表示沒(méi)有數(shù)的時(shí)候

而nums里的第i個(gè)數(shù)下標(biāo)是i-1

因此，正確的狀態(tài)轉(zhuǎn)移方程是：

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

我花時(shí)間比較多的點(diǎn)在于，我錯(cuò)誤寫成了如下：

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

明確這些了來(lái)寫代碼

class Solution {
public:
    /*
    A: 所有采用+的數(shù)的集合，B：所有采用-的數(shù)的集合
    sum(A) - sum(B) = S
    sum(A) + sum(A) = S + sum(B) + sum(A)
    sum(A) = (S + sum)/2
    */

    int findTargetSumWays(vector<int>& nums, int S) {
        long sum = 0;
        for(auto x:nums) sum+=x;
        if (S > sum || (sum + S)%2!=0) return 0;
        int target = (sum + S)/2;
        return subset(nums, target);
    }

    int subset(vector<int>& nums, int target){
        //背包問(wèn)題
        //dp[i][j]: 在前i個(gè)數(shù)中選擇恰好裝滿背包j有幾種方法
        //dp[nums.size()-1][target]是結(jié)果
        //dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]] 第i個(gè)物品不裝的方案?jìng)€(gè)數(shù)：dp[i-1][j]，第i個(gè)物品裝的方案?jìng)€(gè)數(shù)：dp[i-1][j-nums[i-1]]

        //初始化
        int size = nums.size();
        vector<vector<int>> dp(size+1, vector<int>(target+1, 0));
        for(int i = 0; i <= size; i++) dp[i][0] = 1;
        for(int i = 1; i <= size; i++){
            for(int j = 0; j <= target; j++){
                if (j-nums[i-1]>=0)
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
                else
                    dp[i][j] = dp[i-1][j];
            }
        }
        return dp[nums.size()][target];
    }
};

動(dòng)態(tài)規(guī)劃的維度壓縮

是的，沒(méi)有錯(cuò)！

可以看出，每個(gè)dp[i]僅依賴于dp[i-1]，那這就是可以做路徑壓縮的呀小可愛(ài)們

道理是這樣：即然我要更新dp[i]，只需要dp[i-1]的信息，那我就可以無(wú)腦刪掉關(guān)于[i]的下標(biāo)，使用一維數(shù)組實(shí)現(xiàn)維度壓縮

這個(gè)時(shí)候狀態(tài)議程變成了：

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

為了保證我每次迭代的時(shí)候，dp[j]和dp[j-nums[i-1]]都是上一輪的值，j需要從后往前更新。即我更新dp[j]時(shí)，dp[j-nums[i-1]]是i-1輪的值，而非第i輪的值，那j只能從大往小走了，要從小往大走的話，上一輪的dp[j-nums[i-1]]就沒(méi)了

道理理清了，來(lái)寫代碼

class Solution {
public:
    /*
    A: 所有采用+的數(shù)的集合，B：所有采用-的數(shù)的集合
    sum(A) - sum(B) = S
    sum(A) + sum(A) = S + sum(B) + sum(A)
    sum(A) = (S + sum)/2
    */

    int findTargetSumWays(vector<int>& nums, int S) {
        long sum = 0;
        for(auto x:nums) sum+=x;
        if (S > sum || (sum + S)%2!=0) return 0;
        int target = (sum + S)/2;
        return subset(nums, target);
    }

    int subset(vector<int>& nums, int target){
        //背包問(wèn)題
        //dp[i][j]: 在前i個(gè)數(shù)中選擇恰好裝滿背包j有幾種方法
        //dp[nums.size()-1][target]是結(jié)果
        //dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]] 第i個(gè)物品不裝的方案?jìng)€(gè)數(shù)：dp[i-1][j]，第i個(gè)物品裝的方案?jìng)€(gè)數(shù)：dp[i-1][j-nums[i-1]]

        //初始化
        int size = nums.size();
        vector<int> dp(target+1, 0);
        for(int i = 0; i <= size; i++) dp[0] = 1;

        for(int i = 1; i <= size; i++){
            for(int j = target; j >=0; j--){
                if (j-nums[i-1]>=0)
                    dp[j] = dp[j] + dp[j-nums[i-1]];
                else
                    dp[j] = dp[j];
            }
        }
        return dp[target];
    }
};