目錄

前言：

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

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

總結(jié)：

前言：

? ? ? ? ? ? ? ? ?今天我們依然暴打動(dòng)態(tài)規(guī)劃

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

有一堆石頭，用整數(shù)數(shù)組?stones 表示。其中?stones[i] 表示第 i 塊石頭的重量。

每一回合，從中選出任意兩塊石頭，然后將它們一起粉碎。假設(shè)石頭的重量分別為?x 和?y，且?x <= y。那么粉碎的可能結(jié)果如下：

如果?x == y，那么兩塊石頭都會(huì)被完全粉碎；
如果?x != y，那么重量為?x?的石頭將會(huì)完全粉碎，而重量為?y?的石頭新重量為?y-x。
最后，最多只會(huì)剩下一塊 石頭。返回此石頭 最小的可能重量 。如果沒(méi)有石頭剩下，就返回 0。

這個(gè)問(wèn)題其實(shí)很好想：我們?nèi)绾伟咽^盡可能的撞碎呢？

很簡(jiǎn)單，我們?cè)诖篌w上把這些石頭分成重量相似的兩堆，因?yàn)槿绻麅啥咽^的重量相似，那么相撞后就一定會(huì)得到最小的值。

因此從動(dòng)態(tài)分類的角度來(lái)講，我們可以把這道題理解為是? 一個(gè)重量為（sum/2）的背包，我們盡可能的裝背包，之后裝進(jìn)背包的是一堆石頭，未裝進(jìn)背包的是一堆石頭，那么這兩堆石頭相減，就可以得到最小的石頭重量。

那么我們就又把這道題轉(zhuǎn)化為了?裝與不裝的01背包問(wèn)題

其實(shí)這道題和我們前天做的分割等和子集是基本相同的，感興趣的朋友可以去看一下那道題

那么既然是動(dòng)態(tài)規(guī)劃問(wèn)題，我們就繼續(xù)進(jìn)行動(dòng)態(tài)規(guī)劃五部曲：

1.確定dp數(shù)組及其含義：dp[j]? 是背包含量為j的時(shí)候所背的最大價(jià)值（在這里我們重量就是價(jià)值，價(jià)值就是重量）

2.遞推公式? dp[j] = max(dp[j] , dp[ j - stones[i] ]+stones[i])

里層的減是減去容量，外面的加是加上價(jià)值，只不過(guò)是因?yàn)槲覀兊闹亓亢蛢r(jià)值是一樣的

3.確定初始化：全部初始化為0即可?

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
            int sum=0;
            vector<int>dp(1501,0);
        for(int a : stones)
        {
            sum=sum+a;
        }

        int target = sum/2;

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

?在這里我們要特別對(duì)末尾進(jìn)行說(shuō)明，為什么是? ?return sum-dp[target]-dp[target];

其實(shí)很好理解，因?yàn)檫@里的dp數(shù)組是一堆石頭，而我們用sum-dp數(shù)組就得到了另外一堆石頭的重量，再減一次dp數(shù)組，實(shí)際就是模擬兩堆石頭進(jìn)行碰撞。

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

給你一個(gè)非負(fù)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) target 。

向數(shù)組中的每個(gè)整數(shù)前添加?'+' 或 '-' ，然后串聯(lián)起所有整數(shù)，可以構(gòu)造一個(gè) 表達(dá)式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串聯(lián)起來(lái)得到表達(dá)式 "+2-1" 。
返回可以通過(guò)上述方法構(gòu)造的、運(yùn)算結(jié)果等于 target 的不同 表達(dá)式 的數(shù)目。

這道題其實(shí)我們可以這樣理解：?

一共有兩個(gè)集合，兩個(gè)集合分別裝數(shù)字，設(shè)置目標(biāo)值target，詢問(wèn)有幾種可能使得兩個(gè)集合相減的數(shù)字等于target

再優(yōu)化一下：

我們可以把target也作為一個(gè)數(shù)字加到這兩個(gè)集合的待選序列，詢問(wèn)有幾種可能? 使得兩個(gè)集合的值相等

??再轉(zhuǎn)化一下思維：

,而target只有一個(gè)，也就是只能永遠(yuǎn)出現(xiàn)在一側(cè)，另外一側(cè)始終沒(méi)有target，那么我們始終求沒(méi)有target的那一側(cè)不就好了嘛，換句話說(shuō)，不就是在給定集合里面尋找有多少個(gè)集合的值等于（sum+target）/2/

那么我們不就又把這道題轉(zhuǎn)化為了背包問(wèn)題嘛？只不過(guò)以前我們總是在求是否有一種方法能把背包裝滿，現(xiàn)在求的是有多少種方法把背包裝滿。

因此我們按照動(dòng)態(tài)規(guī)劃五部曲走：

1.確定dp數(shù)組的含義：dp[j] 表示填滿容量為j的背包最多有dp[j]種方法，例如dp[2]是指填滿容量為2的背包最多有dp[2]種方法。

2.確定遞推公式：dp[j]+=dp[j-nums[i]];

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for(int a : nums)
        {
            sum=sum+a;
        }

        if((target + sum)%2==1) return 0;
        if(abs(target)>sum) return 0;
        else
        {
              int a = (target + sum) / 2;
              vector<int> dp(a + 1, 0);
             dp[0] = 1;
            for (int i = 0; i < nums.size(); i++) 
            {
               for (int j = a; j >= nums[i]; j--) 
               {
                dp[j] += dp[j - nums[i]];
                }
            }
        return dp[a];
        }
    }
};

總結(jié)：

? ? ? ? 動(dòng)態(tài)規(guī)劃想清楚之后直接爆殺。

如果我的內(nèi)容對(duì)你有幫助，請(qǐng)點(diǎn)贊，評(píng)論，收藏。創(chuàng)作不易，大家的支持就是我堅(jiān)持下去的動(dòng)力！

?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-629793.html

到了這里，關(guān)于【力扣刷題 | 第二十四天】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！