网站上怎么做企业推广,内蒙网站建设seo优化,网站建设创新点,兰州网站建设推荐q479185700顶你关键词#xff1a;动态规划 01背包
一个套路#xff1a;
01背包#xff1a;空间优化之后dp【target1】#xff0c;遍历的时候要逆序遍历完全背包#xff1a;空间优化之后dp【target1】#xff0c;遍历的时候要正序遍历 目录
题目#xff1a;
思路#xff1a;
复杂…关键词动态规划 01背包
一个套路
01背包空间优化之后dp【target1】遍历的时候要逆序遍历完全背包空间优化之后dp【target1】遍历的时候要正序遍历 目录
题目
思路
复杂度计算
代码 题目
思路
这题能想到用01背包并正确用起来有点难哦
这里面有三样东西一些strsm个0和n个1。
我刚开始是希望把strs当作容器把0和1装进strs这个容器里但是不行。
转换思路把m个0和n个1作为两个容器strs里的0和1分别装进这两个容器里。
因为有两个容器所以dp得要两个维度dp[m1][n1]
其他都和一维的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(lmnL) lstrs.size() L所有str的字符总数统计了每个str的01数量
空间复杂度O(mn)
代码
class Solution {
public:int findMaxForm(std::vectorstd::string strs, int m, int n) {std::vectorstd::vectorint dp(m 1, std::vectorint(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];}
};
