算法學(xué)習(xí)——LeetCode力扣動(dòng)態(tài)規(guī)劃篇3

494. 目標(biāo)和

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ù)目。

示例

示例 1：

輸入：nums = [1,1,1,1,1], target = 3
輸出：5
解釋?zhuān)阂还灿?5 種方法讓最終目標(biāo)和為 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
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

輸入：nums = [1], target = 1
輸出：1

提示

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

代碼解析

這道題根本還是回到了在數(shù)組中找到一個(gè)集合，使得該集合與其余部分之差為target，通過(guò)公式推導(dǎo)：
我們可以知道 該集合的值為：（sum-target）/2;

回溯法

目的是找到和為**（sum-target）/2** 的種類(lèi)

class Solution {
public:
    int result = 0;
    void backtracking(vector<int>& nums, int target ,int deep ,int sum)
    {
        if(sum > target)return;
        if(sum == target)result++;
        if(deep == nums.size()) return;
        //從任一點(diǎn)開(kāi)始
        for(int i= deep ; i < nums.size() ;i++)
        {
            backtracking(nums,target , i+1  , sum + nums[i]);
        }
        return;
    }
    int findTargetSumWays(vector<int>& nums, int target) {
       
        int sum = 0 , diff = 0;
        for(auto it:nums) sum += it;
        diff = sum - target;
        if( diff<0 || diff%2==1 ) return 0;
		//回溯找diff/2
        backtracking(nums,diff/2,0 ,0);
        return result;
    }
};

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

1. 背包定義： dp[i][j] , i是使用0-i的元素，j是背包容量，dp[i][j]是使用這么多個(gè)元素恰好湊成j的情況
2. 初始化：dp[0][0]為1,裝滿容量為0的背包，有一種方法。dp[0][j]，看第一個(gè)元素的大小情況，進(jìn)行賦值1(如果第一個(gè)元素為0.則dp[0][0]應(yīng)該為2)，其他層的根據(jù)第一層改變.
3. 遍歷順序：從上往下
4. 遞推公式： dp[i][j]=dp[i-1][j]（不需要num[i]就能夠湊出j的情況）+dp[i-1][j-nums[i]]；（需要num[i]湊出j空間的情況） 最終就能實(shí)現(xiàn)，從0-i元素當(dāng)中組合，得到target的所有情況。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
       
        int sum = 0 , diff = 0;
        for(auto it:nums) sum += it;
        diff = sum - target;
        if( diff<0 || diff%2==1 ) return 0;
        vector<vector<int>>  dp( nums.size() , vector<int>(diff/2 + 1 , 0) ) ;

        dp[0][0] = 1;
        for(int j=0 ; j<(diff)/2+1 ; j++)
            if(j==nums[0]) dp[0][j] += 1;


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

474. 一和零

474. 一和零 - 力扣（LeetCode）

描述

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

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

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

示例

示例 1：

輸入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
輸出：4
解釋?zhuān)鹤疃嘤?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
解釋?zhuān)鹤畲蟮淖蛹?{“0”, “1”} ，所以答案是 2 。

提示

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

代碼解析

動(dòng)態(tài)規(guī)劃（01背包，三級(jí)數(shù)組）

和經(jīng)典的背包問(wèn)題只有一種容量不同，這道題有兩種容量，即選取的字符串子集中的 0 和 1 的數(shù)量上限。

經(jīng)典的背包問(wèn)題可以使用二維動(dòng)態(tài)規(guī)劃求解，兩個(gè)維度分別是物品和容量。這道題有兩種容量，因此需要使用三維動(dòng)態(tài)規(guī)劃求解，三個(gè)維度分別是字符串、0的容量和 1 的容量。

定義三維數(shù)組dp，其中dp[i][j][k] 表示在前 i 個(gè)字符串中，使用 j 個(gè) 0 和 k 個(gè) 1 的情況下最多可以得到的字符串?dāng)?shù)量。
當(dāng) 0 和 1 的容量分別是 j 和 k 時(shí)，考慮以下兩種情況：

• 如果 j< zeros 或 k<ones，則不能選第 i 個(gè)字符串，此時(shí)有 dp[i][j][k] = dp[i?1][j][k]；

• 如果 j ≥ zeros 且 k ≥ones，則如果不選第 i個(gè)字符串，有dp[i][j][k]=dp[i?1][j][k]，如果選第 i個(gè)字符串，有 dp[i][j][k]=dp[i?1][j?zeros][k?ones]+1，dp[i][j][k] 的值應(yīng)取上面兩項(xiàng)中的最大值。

因此狀態(tài)轉(zhuǎn)移方程如下：

class Solution {
public:
    int find_0(string s1)
    {
        int num = 0;
        for(auto it:s1) if(it == '0') num++;
        return num;
    }

    int findMaxForm(vector<string>& strs, int m, int n) {

        vector<vector<vector<int>>>  dp( strs.size() ,vector<vector<int>>( m+1 ,vector<int>( n+1,0) ));
        int num_0 = 0,num_1 = 0;
        num_0 = find_0(strs[0]);
        num_1 = strs[0].size() - num_0;
        for(int j=0 ; j<= m ;j++)
        {
            for(int k=0 ; k<= n ;k++)
            {
               
                if( j>= num_0 && k>= num_1)
                    dp[0][j][k] = 1;
            }
           
        }

        
        for(int i=1 ; i<strs.size() ; i++)
        {
            num_0 = find_0(strs[i]);
            num_1 = strs[i].size() - num_0;
            for(int j=0 ; j<=m ;j++)
            { 
                for(int k=0 ; k<=n ;k++)
                {
                    
                     if( j>= num_0 && k>= num_1)
                        dp[i][j][k] = max( dp[i-1][j][k], dp[i-1][j - num_0][k - num_1] + 1);
                     else
                        dp[i][j][k] = dp[i-1][j][k];
                }
            }
        }
        
        int max_num = 0;
        for(int i=0 ; i<strs.size() ; i++)
        {
            if(dp[i][m][n] > max_num) max_num = dp[i][m][n];
            // cout<<dp[i][m][n]<<' ';
        }
            
        return max_num ;
    }
};

動(dòng)態(tài)規(guī)劃（滑動(dòng)數(shù)組，二級(jí)數(shù)組）

由于dp[i][][] 的每個(gè)元素值的計(jì)算只和dp[i?1][][] 的元素值有關(guān)，因此可以使用滾動(dòng)數(shù)組的方式，去掉 dp 的第一個(gè)維度，將空間復(fù)雜度優(yōu)化到 O(mn)O(mn)。

實(shí)現(xiàn)時(shí)，內(nèi)層循環(huán)需采用倒序遍歷的方式，這種方式保證轉(zhuǎn)移來(lái)的是 dp[i?1][][] 中的元素值。

class Solution {
public:
    int find_0(string s1)
    {
        int num = 0;
        for(auto it:s1) if(it == '0') num++;
        return num;
    }

    int findMaxForm(vector<string>& strs, int m, int n) {

        vector<vector<int>>  dp( m+1 ,vector<int>(n+1,0));

        int num_0 = 0,num_1 = 0;
        for(int i=0 ; i<strs.size() ; i++)
        {
            num_0 = find_0(strs[i]);
            num_1 = strs[i].size() - num_0;
            for(int j=m ; j>=num_0;j--)
            { 
                for(int k=n ; k>=num_1 ;k--)
                {
                    dp[j][k] = max( dp[j][k], dp[j - num_0][k - num_1] + 1);
                }
            }
        }
        return dp[m][n] ;
    }
};

518. 零錢(qián)兌換 II

518. 零錢(qián)兌換 II - 力扣（LeetCode）

描述

給你一個(gè)整數(shù)數(shù)組 coins 表示不同面額的硬幣，另給一個(gè)整數(shù) amount 表示總金額。

請(qǐng)你計(jì)算并返回可以湊成總金額的硬幣組合數(shù)。如果任何硬幣組合都無(wú)法湊出總金額，返回 0 。

假設(shè)每一種面額的硬幣有無(wú)限個(gè)。

題目數(shù)據(jù)保證結(jié)果符合 32 位帶符號(hào)整數(shù)。

示例

示例 1：

輸入：amount = 5, coins = [1, 2, 5]
輸出：4
解釋?zhuān)河兴姆N方式可以湊成總金額：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

輸入：amount = 3, coins = [2]
輸出：0
解釋?zhuān)褐挥妹骖~ 2 的硬幣不能湊成總金額 3 。

示例 3：

輸入：amount = 10, coins = [10]
輸出：1

提示

1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins 中的所有值 互不相同
0 <= amount <= 5000

代碼解析

完全背包

一看到錢(qián)幣數(shù)量不限，就知道這是一個(gè)完全背包。
dp[j]：湊成總金額j的貨幣組合數(shù)為dp[j]

dp[j] （考慮coins[i]的組合總和） 就是所有的dp[j - coins[i]]（不考慮coins[i]）相加。
所以遞推公式：dp[j] += dp[j - coins[i]];

首先dp[0]一定要為1，dp[0] = 1是 遞歸公式的基礎(chǔ)。
從dp[i]的含義上來(lái)講就是，湊成總金額0的貨幣組合數(shù)為1。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-851359.html

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp( amount+1 , 0 );

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

到了這里，關(guān)于算法學(xué)習(xí)——LeetCode力扣動(dòng)態(tài)規(guī)劃篇3（494. 目標(biāo)和、474. 一和零、518. 零錢(qián)兌換 II）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！