日照网站建设网站超云seo优化
关键词：动态规划 01背包
一个套路：
- 01背包：空间优化之后dp【target+1】，遍历的时候要逆序遍历
- 完全背包：空间优化之后dp【target+1】，遍历的时候要正序遍历
目录
题目：
思路：
复杂度计算：
代码：
题目：
思路：
这题能想到用01背包并正确用起来有点难哦！
这里面有三样东西，一些strs，m个0和n个1。
我刚开始是希望把strs当作容器，把0和1装进strs这个容器里，但是不行。
转换思路：把m个0和n个1作为两个容器，strs里的0和1分别装进这两个容器里。
因为有两个容器，所以dp得要两个维度dp[m+1][n+1]
其他都和一维的01背包一样
状态：dp[j][k] 前i个str中，使用 j个 0 和 k 个 1 的情况下最多可以得到的字符串数量。
转移方程：dp[j][k]=max(dp[j][k],dp[j-zeros][k-ones]+1)【zeros、ones：第i个str0和1的个数】
- 如果选dp[j][k]：不要第i个str，维持上一个str的状态。
- 如果选dp[j-zeros][k-ones]+1：要第i个str，数量+1。
初始化：dp[j][k]=0 因为是求最大
复杂度计算：
时间复杂度O(lmn+L) l=strs.size() L=所有str的字符总数（统计了每个str的01数量）
空间复杂度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];}
};