湛江网站关键字优化,网站开发 职位描述,app封装平台,示范校建设平台网站典型案例139.单词拆分 思路#xff1a;将字符串s看作为背包容量#xff0c;从字符串中获取物品#xff0c;刚好满足背包容量的过程#xff0c;因为可以从字符串中多次取值#xff0c;相当于物品的数量是不限制#xff0c;这就是一个完全背包的问题#xff01;这个题有个关键点将字符串s看作为背包容量从字符串中获取物品刚好满足背包容量的过程因为可以从字符串中多次取值相当于物品的数量是不限制这就是一个完全背包的问题这个题有个关键点在于遍历物品的时候分为两部分一部分是前j个部分判断这部分是否是物品中的东西另外一部分就是判断剩下这部分是否是物品中的东西相当于把一个子串也要拆分一个大的串就是多个子串组成并且这些子串还是有顺序的 class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring myset(wordDict.begin(),wordDict.end());vectorbool dp(s.size()1,false);dp[0]true;for(int i1;is.size();i)//遍历背包{for(int j0;ji;j)//遍历物品{string words.substr(j,i-j);if(myset.find(word)!myset.end()dp[j]true){dp[i]true;}}}return dp[s.size()];}
};56.携带矿石资源 思路将每个类型的数量进行展开最后变成01背包问题但是展开的时候要区分应该在01遍历的过程中这十分重要! #includeiostream
#includevector
using namespace std;
int main()
{int bagweight,n;cinbagweightn;vectorint weight(n,0);vectorint value(n,0);vectorint nums(n,0);for(int i0;in;i)cinweight[i];for(int i0;in;i)cinvalue[i];for(int i0;in;i)cinnums[i];vectorint dp(bagweight1,0);for(int i0;in;i){for(int jbagweight;jweight[i];j--){//01背包的套路//相当于利用一个循环吧把每次都给取开for(int k1;knums[i](j-k*weight[i])0;k){dp[j]max(dp[j],dp[j-k*weight[i]]k*value[i]);}}}coutdp[bagweight]endl;
}
