1. 題目

在計算機界中，我們總是追求用有限的資源獲取最大的收益。

現在，假設你分別支配著 m 個 0 和 n 個 1。另外，還有一個僅包含 0 和 1 字符串的數組。

你的任務是使用給定的 m 個 0 和 n 個 1 ，找到能拼出存在于數組中的字符串的最大數量。每個 0 和 1 至多被使用一次。

注意: 給定 0 和 1 的數量都不會超過 100。 給定字符串數組的長度不會超過 600。示例 1: 輸入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3 輸出: 4 解釋: 總共 4 個字符串可以通過 5 個 0 和 3 個 1 拼出， 即 "10","0001","1","0" 。示例 2: 輸入: Array = {"10", "0", "1"}, m = 1, n = 1 輸出: 2 解釋: 你可以拼出 "10"，但之后就沒有剩余數字了。 更好的選擇是拼出 "0" 和 "1" 。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/ones-and-zeroes
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 0-1背包的變種，兩個維度，背包容量為m,n, 求能裝下的單詞最多

class Solution { public:int findMaxForm(vector<string>& strs, int m, int n) {int i, j, k, one, zero, len = strs.size(), maxcount = 0;vector<vector<int>> dp(m+1,vector<int>(n+1,-1));//dp[i][j] 表示使用i個0，j個1 時，對應的最大單詞數個數dp[0][0] = 0;//初始化for(i = 0; i < len; ++i)//遍歷每個單詞{one = count01(strs[i]);zero = strs[i].size()-one;for(j = m-zero; j >= 0; --j){ //逆序遍歷，+one,zero后新生成的狀態不會干擾本次for(k = n-one; k >= 0; --k){if(dp[j][k] != -1)//存在的狀態{ //轉移到的狀態 dp[j+zero][k+one]dp[j+zero][k+one] = max(dp[j+zero][k+one], dp[j][k]+1);maxcount = max(maxcount, dp[j+zero][k+one]);}}}}return maxcount; }int count01(string &s){int one = 0;for(int i = 0; i < s.size(); ++i){if(s[i]=='1') one++;}return one;} };

總結

以上是生活随笔為你收集整理的LeetCode 474. 一和零（01背包动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。