1049.最后一塊石頭的重量II

力扣題目鏈接(opens new window)

題目難度：中等

有一堆石頭，每塊石頭的重量都是正整數(shù)。

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

如果?x == y，那么兩塊石頭都會(huì)被完全粉碎；

如果?x != y，那么重量為?x?的石頭將會(huì)完全粉碎，而重量為?y?的石頭新重量為?y-x。

最后，最多只會(huì)剩下一塊石頭。返回此石頭最小的可能重量。如果沒有石頭剩下，就返回 0。

示例：

• 輸入：[2,7,4,1,8,1]
• 輸出：1

解釋：

• 組合 2 和 4，得到 2，所以數(shù)組轉(zhuǎn)化為 [2,7,1,8,1]，
• 組合 7 和 8，得到 1，所以數(shù)組轉(zhuǎn)化為 [2,1,1,1]，
• 組合 2 和 1，得到 1，所以數(shù)組轉(zhuǎn)化為 [1,1,1]，
• 組合 1 和 1，得到 0，所以數(shù)組轉(zhuǎn)化為 [1]，這就是最優(yōu)值。

提示：

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 1000

看到題目的第一想法

? ? ? ? 我會(huì)想著去相減獲取最小的值

? ? ? ? dp存最小值

? ? ? ? 01背包獲取的是最大值

看到代碼隨想錄之后的想法

????????01背包獲取的是最大值

? ? ? ? 將所有的石頭加起來，獲取石頭總和的一半

? ? ? ? 背包:? ?選中石頭0~i 達(dá)到背包容量為石頭總和的一半的最大值是多少

? ? ? ? weight[i] 石頭大小

? ? ? ? value[j] 石頭大小

? ? ? ? 動(dòng)規(guī)五部曲，很快的寫出解題思路

? ? ? ? 1確定dp數(shù)組以及對(duì)應(yīng)下標(biāo)的含義

????????dp[j] 代表選中0~i達(dá)到背包容量j時(shí)的最大值

? ? ? ?背包容量：0~石頭總和的一半

????????2確定遞推公式

? ? ? ? dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i]);

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

? ? ? ? 都為0

? ? ? ? 4確定遍歷順序

? ? ? ? 先物品后背包

????????從后往前

????????5手動(dòng)推導(dǎo)dp數(shù)組

? ? ? ? 6打印dp數(shù)組

? ? ? ??

自己實(shí)現(xiàn)過程中遇到的困難

? ? ? ? return sum-2dp[target]

class Solution {
    public int lastStoneWeightII(int[] stones) {
        // 我的思路 想直接獲取最小值是錯(cuò)誤的,  01背包獲取的是最大值
        // dp[j] 選中0~i塊石頭在j這個(gè)空間內(nèi)的最小重量值
        //卡哥思路
        // 本題返回的是最小重量，也就是差值的最小重量
        // 可以把所有石頭重量求和，獲取總重量
        // 當(dāng)我們可以達(dá)到總重量的一半時(shí)，就為0
        // 求當(dāng)背包重量到達(dá)總重量一半時(shí)，背包可以容納的最大值，就轉(zhuǎn)換成背包問題了
        // dp數(shù)組的確定以及每個(gè)下標(biāo)的含義
        // 選中0~i塊石頭 ，當(dāng)背包到達(dá)容量j時(shí)可以容納的最大值為多少
        // 確定遞推公式
        // 上一層 or 上一層-當(dāng)前層的weight后加上當(dāng)前層的值
        // dp[j] = Math.max(dp[j],dp[j-stones[j]]+stones[i]);
        // dp的初始化
        // 開始都為0，從石頭0開始逐個(gè)遍歷
        // 確定遍歷順序
        // 從后往前
        // 手動(dòng)推導(dǎo)dp數(shù)組
        int sum=0;
        for(int i=0;i<stones.length;i++){
            sum+=stones[i];
        }
        int target = sum/2;
        int dp[] = new int[target+1];
        for(int i=0;i<stones.length;i++){
            for(int j=target;j>=stones[i];j--){
                dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-2*dp[target];
    }
}

494.目標(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ù)組非空，且長度不會(huì)超過 20 。
• 初始的數(shù)組的和不會(huì)超過 1000 。
• 保證返回的最終結(jié)果能被 32 位整數(shù)存下。

看到題目的第一想法

? ? ? ? 想著用dp，但沒思路

看到代碼隨想錄之后的想法

? ? ? ? left+right = sum

? ? ? ? left-right = target

? ? ? ? 2left = sum+target

? ? ? ? 則left = (sum+target)/2

? ? ? ? 則 我們需要計(jì)算的是

????????達(dá)到目標(biāo)和為left的總的方法數(shù)

????????01背包獲取的是最大值

? ? ? ? 將所有的石頭加起來，獲取石頭總和的一半

? ? ? ? 背包:? ?選中0~i 達(dá)到目標(biāo)和為j 有多少種方法

? ? ? ?

? ? ? ? 動(dòng)規(guī)五部曲，很快的寫出解題思路

? ? ? ? 1確定dp數(shù)組以及對(duì)應(yīng)下標(biāo)的含義

????????dp[j] 代表選中0~i達(dá)到背包容量j時(shí)有多少種方法

? ? ? ?背包容量：0~left

????????2確定遞推公式

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

? ? ? ? 若當(dāng)前選中的為nums[i] 則需要找到dp[j-nums[i]]種方法，才能湊成 j?

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

? ? ? ? dp[0]=1? ? 因?yàn)?最開始選中的dp[nums[0]]，有dp[0]種方法湊成?則dp[0]+dp[nums[0]] = 1

? ? ? ? 4確定遍歷順序

? ? ? ? 先物品后背包

????????從后往前

????????5手動(dòng)推導(dǎo)dp數(shù)組

? ? ? ? 6打印dp數(shù)組

? ? ? ??

自己實(shí)現(xiàn)過程中遇到的困難

? ? ? ? 從? j=nums[i] 開始? ，到j(luò)<=left 結(jié)束

? ? ? ? 看有多少種方法湊成left

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        // 讓nums中的和等于sum
        // 觀察一下關(guān)系
        // left-right = target
        // left 為左半邊的和，right為右半邊的和
        // left+right = sum
        // right = sum-left
        // target = left-sum+left
        // 2 left = target+sum
        // left = (target+sum)/2
        // dp數(shù)組 
        // 確定dp數(shù)組和每個(gè)下標(biāo)的含義
        // 背包 0~i之間 填滿j的最大空間
        // 求出left，計(jì)算0~i之間能滿足空間j的數(shù)量 j屬于0~left
        // 確定遞推公式
        // 代表能達(dá)到dp[j]
        // 選中nums[i] 若要滿足填滿空間j ，則需要 num[i]的值+dp[j-nums[i]] 這么多個(gè)才能填滿
        // 在上一層的dp[j]的基礎(chǔ)上加上dp[j-nums[i]] 就是這一層能完成j的總數(shù)了
        // 每一行是i 每一列是j 到第i行時(shí)，從0~i-1得到的結(jié)果中判斷第i行的nums[i] 有多少個(gè)可以滿足j
        // dp[j]+=dp[j-nums[i]]
        // 把之前的能達(dá)成的數(shù)量都加上
        // dp數(shù)組初始化
        // 從后往前，同時(shí)dp[0]=1
        // 若nums[0] = j ，則dp[j] += dp[j-nums[0]] = dp[0] = 1 滿足j的只有1個(gè)
        // dp數(shù)組遍歷順序
        // 從后往前
        // 舉例推導(dǎo)dp數(shù)組
        // 
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        if((sum+target)%2==1){
            return 0;
        }
        //這個(gè)邊界條件沒注意到
        if(Math.abs(target)>sum){
            return 0;
        }
        int left = (sum+target)/2;
        int[] dp = new int[left+1];
        dp[0] = 1;
        for(int i=0;i<nums.length;i++){
            //前面的j 都比nums[i] 要小，無法用nums[i]構(gòu)成j 
            for(int j=left;j>=nums[i];j--){
                dp[j]=dp[j]+dp[j-nums[i]];
            }
        }
        return dp[left];
    }
}

474.一和零(第二次)

力扣題目鏈接(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

看到題目的第一想法

? ? ? ? 想著用dp，

? ? ? ? 1 不知道怎么處理這些string

? ? ? ? 2 這里有二維? 一個(gè)m 一個(gè)n

看到代碼隨想錄之后的想法

? ? ? ? 遍歷字符數(shù)組，看每個(gè)字符串中0 和1 的個(gè)數(shù)

? ? ? ? 背包:? ?選中(0,0)~(i,j)?達(dá)到目標(biāo)和為(m,n) 的子集的個(gè)數(shù)

? ? ? ?weight 為 0和1 的個(gè)數(shù)

? ? ? ? value 統(tǒng)一為1 選中則+1

????????動(dòng)規(guī)五部曲，很快的寫出解題思路

? ? ? ? 1確定dp數(shù)組以及對(duì)應(yīng)下標(biāo)的含義

????????dp[i][j] i代表m

? ? ? ?背包容量：0，0 ~ （m,n）

????????2確定遞推公式

? ? ? ? 若不選則還是之前的

? ? ? ? 若選中則+1

? ? ? ? dp[I][j]=Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1)

? ? ? ? 若當(dāng)前選中的為str[i] 則需要找到dp[i-0的個(gè)數(shù)][j-1的個(gè)數(shù)]種方法，才能湊成 dp[i][j]

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

? ? ? ? 都為0

? ? ? ? 4確定遍歷順序

? ? ? ? 先物品后背包

????????從后往前

????????5手動(dòng)推導(dǎo)dp數(shù)組

? ? ? ? 6打印dp數(shù)組

? ? ? ??

自己實(shí)現(xiàn)過程中遇到的困難

? ? ? ?用string轉(zhuǎn)成char數(shù)組來記錄0的個(gè)數(shù)和1 的個(gè)數(shù)文章來源地址http://www.zghlxwxcb.cn/news/detail-797164.html

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        // str 的最大的子集的長度
        // 使用一個(gè)map記錄數(shù)組有多少個(gè)0和1？
        // 卡哥思路 dp 用一個(gè)二維數(shù)組，dp[m][n] 記錄 滿足子集m個(gè)0和n個(gè)1的最大個(gè)數(shù)
        // 背包 滿足 m個(gè)0和n個(gè)1 的個(gè)數(shù)？
        // 計(jì)算有多少個(gè)0 和多少個(gè)1
        // 子集中的每個(gè)元素 最多有m個(gè)0 和n個(gè)1 
        // dp數(shù)組和每個(gè)下標(biāo)的定義
        // dp記錄填滿背包的[m][n]最大個(gè)數(shù)
        // 確定遞推公式
        // dp[m][n]=Math.max(dp[m][n],dp[m-oneNum][n-oneNum]);
        // dp數(shù)組的初始化
        // 都為0
        // 確定遍歷順序
        // 從后往前
        // 手動(dòng)推導(dǎo)dp數(shù)組
        int[][] dp = new int[m+1][n+1];
        for(String str:strs){
            int zeroNum=0;
            int oneNum=0;
            for(int i=0;i<str.length();i++){
                if(str.charAt(i)=='0'){
                    zeroNum++;
                }else{
                    oneNum++;
                }
            }
            for(int i=m;i>=zeroNum;i--){
                for(int j=n;j>=oneNum;j--){
                    dp[i][j] = Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
                }
            }
        }
        return dp[m][n];
    }
}

到了這里，關(guān)于動(dòng)態(tài)規(guī)劃day05（背包問題）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！