LeetCode 474 Ones and Zeroes 滚动数组优化DP
2022/6/4 23:22:48
本文主要是介绍LeetCode 474 Ones and Zeroes 滚动数组优化DP,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
You are given an array of binary strings strs
and two integers m
and n
.
Return the size of the largest subset of strs
such that there are at most m
\(0\)'s and n
\(1\)'s in the subset.
A set \(x\) is a subset of a set \(y\) if all elements of \(x\) are also elements of \(y\).
Solution
考虑朴素的转移,设 \(dp[i][j][k]\) 表示在前 \(i\) 个字符串中,\(0\) 个数上限为 \(j\),\(1\) 个数上限为 \(k\) 时的最大子集个数。那么如何转移呢?类似于背包问题:我们或者不选当前的,也就是从上一层继承答案;或者选择当前的,进行答案的更新:
\[dp[i][j][k] = \max(dp[i-1][j][k],dp[i][j-n_0][k-n_1]+1) \]其中 \(n_0,n_1\) 分别代表当前串中 \(0,1\) 的个数。
观察一下,我们此时的答案,只需要从上一层转移。所以用滚动数组来滚去一维。但此时需要注意的是,我们需要倒序来更新,否则就会将之前的上一层给抹去。
点击查看代码
class Solution { private: int dp[102][102]; public: int findMaxForm(vector<string>& strs, int m, int n) { int l = strs.size(); for(int i=0;i<l;i++){ int n0 = 0, n1 = 0; for(int j=0;j<strs[i].length();j++){ if(strs[i][j]=='0')n0++; else n1++; } for(int j=m;j>=n0;j--){ for(int k=n;k>=n1;k--){ dp[j][k] = max(dp[j][k], dp[j-n0][k-n1]+1); } } } return dp[m][n]; } };
这篇关于LeetCode 474 Ones and Zeroes 滚动数组优化DP的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-24怎么切换 Git 项目的远程仓库地址?-icode9专业技术文章分享
- 2024-12-24怎么更改 Git 远程仓库的名称?-icode9专业技术文章分享
- 2024-12-24更改 Git 本地分支关联的远程分支是什么命令?-icode9专业技术文章分享
- 2024-12-24uniapp 连接之后会被立马断开是什么原因?-icode9专业技术文章分享
- 2024-12-24cdn 路径可以指定规则映射吗?-icode9专业技术文章分享
- 2024-12-24CAP:Serverless?+AI?让应用开发更简单
- 2024-12-23新能源车企如何通过CRM工具优化客户关系管理,增强客户忠诚度与品牌影响力
- 2024-12-23原创tauri2.1+vite6.0+rust+arco客户端os平台系统|tauri2+rust桌面os管理
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享