当前位置: 首页 > news >正文

房地产公司名称大全谷歌seo查询

房地产公司名称大全,谷歌seo查询,个人blog网站开发,温州公司网站开发关键词:动态规划 01背包 一个套路: 01背包:空间优化之后dp【target1】,遍历的时候要逆序遍历完全背包:空间优化之后dp【target1】,遍历的时候要正序遍历 目录 题目: 思路: 复杂…

关键词:动态规划 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];}
};

http://www.zhongyajixie.com/news/18980.html

相关文章:

  • 同企网站建设做网站网站站长工具
  • 个人做财经类网站北京seo服务销售
  • 网站备案最快多久哈尔滨seo优化
  • description 网站描述下载百度app下载
  • 沧浪网站建设方案优化网站排名茂名厂商
  • wordpress 评论 电话汕头seo网络推广服务
  • 科技网站建设分析南京seo域名
  • 电脑网站显示安全证书有问题怎么解决三只松鼠软文范例500字
  • 建设海外网站微信推广方案
  • 工业和信息化部网站备案系统怎么登录万网域名查询官网
  • 网站备案 多ip互联网推广有哪些方式
  • 科普网站建设方案书互联网怎么赚钱
  • 六盘水住房和城乡建设部网站外贸推广优化公司
  • 自己怎么样建网站视频北京网站优化实战
  • 无极网站建设如何在百度上发广告
  • 怎么做网站咨询企业网站设计论文
  • 哈尔滨网站域名归那里管广州百度推广客服电话
  • 品牌网站建设小蝌蚪1阜新网站seo
  • 市住房和城乡建设委员会官方网站关键词怎么做快速的有排名
  • 本网站正在建设升级中网站如何优化流程
  • 静态网页制作代码html可复制西安seo关键词排名
  • 建立网站和新媒体信息发布制度线上营销模式
  • 企业邮箱域名解析乐天seo视频教程
  • 终端平台网站建设百度招聘平台
  • 网站开发课程设计参考文献深圳百度快照优化
  • 手机网站域名如何解析网络优化app哪个好
  • 网站开发与网站建设百度网页版入口链接
  • 我想建立一个网站淘宝网页版
  • 在godaddy做网站贵吗软文是什么意思?
  • 购物网站策划建设方案承德seo