關(guān)鍵詞：動態(tài)規(guī)劃 01背包

一個套路：

• 01背包：空間優(yōu)化之后dp【target+1】，遍歷的時候要逆序遍歷
• 完全背包：空間優(yōu)化之后dp【target+1】，遍歷的時候要正序遍歷

---

?

目錄

題目：

思路：

復(fù)雜度計算：

代碼：

---

題目：

?

思路：

這題能想到用01背包并正確用起來有點難哦！

這里面有三樣?xùn)|西，一些strs，m個0和n個1。

我剛開始是希望把strs當(dāng)作容器，把0和1裝進(jìn)strs這個容器里，但是不行。

轉(zhuǎn)換思路：把m個0和n個1作為兩個容器，strs里的0和1分別裝進(jìn)這兩個容器里。

因為有兩個容器，所以dp得要兩個維度dp[m+1][n+1]

其他都和一維的01背包一樣

狀態(tài)：dp[j][k] 前i個str中，使用?j個?0?和?k?個?1?的情況下最多可以得到的字符串?dāng)?shù)量。

轉(zhuǎn)移方程：dp[j][k]=max(dp[j][k],dp[j-zeros][k-ones]+1)【zeros、ones：第i個str0和1的個數(shù)】

• 如果選dp[j][k]：不要第i個str，維持上一個str的狀態(tài)。
• 如果選dp[j-zeros][k-ones]+1：要第i個str，數(shù)量+1。

初始化：dp[j][k]=0 因為是求最大

復(fù)雜度計算：

時間復(fù)雜度O(lmn+L) l=strs.size() L=所有str的字符總數(shù)（統(tǒng)計了每個str的01數(shù)量）

空間復(fù)雜度O(mn)

代碼：

class Solution {
public:int findMaxForm(std::vector<std::string>& strs, int m, int n) {std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));for (const auto& str:strs){int zeros = 0, ones = 0;for (const auto& c : str){if (c == '0')++zeros;else ++ones;}for (int j = m; j >= zeros; --j){for (int k = n; k >= ones; --k){dp[j][k] = std::max(dp[j][k], dp[j - zeros][k - ones] + 1);}}}return dp[m][n];}
};