江苏龙网

  1. 首页 > 人文 > >

算法萌新如何学好动态规划（3）( 九 )


C++ 代码实现class Solution {public:vector > f;int findMaxForm(vectorfor(int i = 0; i <= m; i++)f[i].resize(n+1);for(int i = 0; i < strs.size(); i++) {int a = 0, b = 0;for(char c:strs[i]) {if(c == '0') a++;else b++;}for(int j = m; j >= a; j--)for(int k = n; k >= b; k--)f[j][k] = max(f[j][k], f[j-a][k-b] + 1);}return f[m][n];}};总结讲解完上述五道例题后 ， 我们可以发现「背包问题」的核心难点在于识别出这是一道「背包问题」 。 识别出是「背包问题」后 ， 我们只需要观察每一个物品最多能取的次数 ， 然后对应到具体的「0/1 背包」、「完全背包」、「多重背包」模型上即可推出对应的「DP 状态」以及「DP 转移方程」 。
为了方便大家后续查阅 ， 现将上述三个背包模型总结如下：
算法萌新如何学好动态规划（3）文章插图
最后 ， 希望大家能将本文的内容与算法萌新如何学好动态规划（2） 中所讲解的「线性 DP」进行统一记忆与理解 ， 在之后遇到「线性 DP」问题时可以参考这四类基础模型（LIS、LCS、数字三角形、背包） ， 实现更快速地解题！
本文作者：Gene_Liu
【算法萌新如何学好动态规划（3）】声明：本文归 “力扣” 版权所有 ， 如需转载请联系 。 文章封面图来源于网络 ， 如有侵权联系删除 。


推荐阅读


上一篇：新人必看，一个接触币圈2年的人花钱买来的教训

下一篇：MIUI 12.5开启内测报名：首批支持21款机型！今晚发布后开始推送