題目

474. 一和零

中等

相關標簽

數組? ?字符串? ?動態(tài)規(guī)劃

給你一個二進制字符串數組?strs?和兩個整數?m?和?n?。

請你找出并返回?strs?的最大子集的長度，該子集中?最多?有?m?個?0?和?n?個?1?。

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

示例 1：

輸入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
輸出：4
解釋：最多有 5 個 0 和 3 個 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他滿足題意但較小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不滿足題意，因為它含 4 個 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

思路和解題方法

• 定義一個二維動態(tài)規(guī)劃數組?dp，其中?dp[i][j]?表示當背包容量為?i?個 0 和?j?個 1 時，所能選擇的字符串的最大數量。
• 對于每個字符串?str，統(tǒng)計其中 0 和 1 的數量，分別記為?zeroNum?和?oneNum。
• 使用雙重循環(huán)遍歷背包容量?i?和?j，從大到小遍歷，以確保在更新?dp[i][j]?時使用的是上一輪循環(huán)中的值。具體地，在第二重循環(huán)中，對于當前的?i?和?j，有兩種選擇：
  • 不選擇當前字符串，此時?dp[i][j]?不變；
  • 選擇當前字符串，此時需要將?i?減去?zeroNum，將?j?減去?oneNum，并將?dp[i-zeroNum][j-oneNum]?加上 1，表示選擇當前字符串后的最大數量。
• 在雙重循環(huán)結束后，dp[m][n]?即為所求。

復雜度

????????時間復雜度:

????????????????O(k*m*n)

????????時間復雜度：該算法使用了二維動態(tài)規(guī)劃數組，對于每個字符串需要遍歷一次整個數組，因此時間復雜度為 O(k * m * n)，其中 k =?len(strs) 表示字符串數組的長度。

????????空間復雜度

????????????????O(m*n)

????????空間復雜度：該算法使用了一個二維動態(tài)規(guī)劃數組，因此空間復雜度為 O(m * n)。需要注意的是，在實際代碼中，我們可以將二維數組優(yōu)化為一維數組，從而將空間復雜度降低到 O(n)。

c++ 代碼

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        // 創(chuàng)建動態(tài)規(guī)劃數組 dp，大小為 (m+1) x (n+1)，并將所有元素初始化為 0
        vector<vector<int>> dp (m+1,vector<int> (n+1,0));
        
        // 遍歷字符串數組 strs
        for(string str :strs)
        {
            // 統(tǒng)計當前字符串中 0 和 1 的個數
            int oneNum = 0,zeroNum = 0;
            for(char c:str) if(c == '0') zeroNum++; else oneNum++;
            
            // 使用雙重循環(huán)遍歷動態(tài)規(guī)劃數組 dp
            for(int i = m;i>=zeroNum;i--) // 遍歷背包容量 m
                for(int j = n;j>=oneNum;j--) // 遍歷背包容量 n
                {
                    // 如果當前字符串可以被放入背包中，更新 dp[i][j] 的值為 dp[i-zeroNum][j-oneNum] + 1
                    // 表示容量為 i、j 的背包所能裝載的最大字符串數量
                    dp[i][j] = max(dp[i][j],dp[i-zeroNum][j-oneNum] + 1);
                }
        }
        
        // 返回容量為 m、n 的背包所能裝載的最大字符串數量
        return dp[m][n];
    }
};

覺得有用的話可以點點贊，支持一下。

如果愿意的話關注一下。會對你有更多的幫助。

每天都會不定時更新哦? >人<? 。文章來源地址http://www.zghlxwxcb.cn/news/detail-741470.html

到了這里，關于力扣第474題 一和零 c++ 動態(tài)規(guī)劃 01背包的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！