代码随想录算法训练营第四十四天-139.单词拆分、56.携带矿石资源-香港服务器租用

代码随想录算法训练营第四十四天-139.单词拆分、56.携带矿石资源

发布时间：2024-03-03 06:03:45 分类：帮助文档

代码随想录算法训练营第四十四天|139.单词拆分、56.携带矿石资源 139.单词拆分思路：将字符串s看作为背包容量，从字符串中获取物品，刚好满足背包容量的过程，因为可以从字符串中多次取值，相当于物品的数量是不限制，这就是一个完全背包的问题！这个题有个关键点，在于遍历物品的时候，分为两部分，一部分是前j个部分，判断这部分是否是物品中的东西，另外一部分就是判断剩下这部分是否是物品中的东西，相当于把一个子串也要拆分！一个大的串，就是多个子串组成，并且这些子串还是有顺序的！ class Solution { public: bool wordBreak(string s, vector& wordDict) { unordered_set myset(wordDict.begin(),wordDict.end()); vector dp(s.size()+1,false); dp[0]=true; for(int i=1;i<=s.size();++i)//遍历背包 { for(int j=0;j<=i;++j)//遍历物品 { string word=s.substr(j,i-j); if(myset.find(word)!=myset.end()&&dp[j]==true) { dp[i]=true; } } } return dp[s.size()]; } }; 56.携带矿石资源思路：将每个类型的数量进行展开，最后变成01背包问题，但是展开的时候，要区分，应该在01遍历的过程中，这十分重要! #include #include using namespace std; int main() { int bagweight,n; cin>>bagweight>>n; vector weight(n,0); vector value(n,0); vector nums(n,0); for(int i=0;i>weight[i]; for(int i=0;i>value[i]; for(int i=0;i>nums[i]; vector dp(bagweight+1,0); for(int i=0;i=weight[i];j--) { //01背包的套路 //相当于利用一个循环吧，把每次都给取开 for(int k=1;k<=nums[i]&&(j-k*weight[i])>=0;k++) { dp[j]=max(dp[j],dp[j-k*weight[i]]+k*value[i]); } } } cout<

上一篇戴尔R730服务器设置管理IP（iDRAC）和安装系统

下一篇打造专属多人游戏天地：如何自建幻兽帕鲁Palworld服务器