本文主要是介绍代码随想录算法训练营第四十六天,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
昨天媳妇发烧啦,和他一顿激烈讨论该不该母乳,目前一切良好,题目在单位做完了,但是有个地方想在家里测试一下。
139.单词拆分
要注意先背包后物品,并且物品是变化的,不是直接用wordDict
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace ::std;class Solution
{
public:bool wordBreak(string s, vector<string> &wordDict){unordered_set<string> WD(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, 0);dp[0] = 1;for (int j = 1; j < s.size() + 1; j++){for (int i = 0; i < j; i++){ // 这里的遍历物品还需要思考一下,不太像正常的物品string str = s.substr(i, j - i);if (WD.find(str) != WD.end() && dp[i] == true){dp[j] = true;for (int ii = 0; ii < s.size() + 1; ii++){cout << dp[ii] << ' ';}cout << "end" << endl;cout << j << endl;cout << str << endl;}}}// printreturn dp[s.size()];}
};
int main()
{Solution syz;string s1 = "applepenapple";vector<string> wordDict1;string a1 = "apple";string a2 = "pen";wordDict1.push_back(a1);wordDict1.push_back(a2);syz.wordBreak(s1, wordDict1);return 0;
}
这里想试个东西,总感觉s.substr(j-i)的长度不太对。
这里真的用的好巧啊,例子用applepenapple。
//首先dp[0]是1毋庸置疑,然后j = 5,即长度5时出现第二个dp[5] = 1,实际上s[5] = p,刚好是下一个开头
1 0 0 0 0 1 0 0 0 0 0 0 0 0 end
5
apple
//然后j = 8的时候,即长度3时,出现第三个dp[8] = 1,s[8] = a,循环上了。
1 0 0 0 0 1 0 0 1 0 0 0 0 0 end
8
pen
1 0 0 0 0 1 0 0 1 0 0 0 0 1 end
13
apple
想说的就是,正好dp[x]中的x,是下一个起始位,所以没有那么多的±1来对齐的问题。最后直接看dp[s.size()]即可。
动态规划:关于多重背包,你该了解这些!
卡码网第56题 (opens new window)
#include<iostream>
#include<vector>
using namespace::std;
int main(){int C;int N;cin >> C >> N;vector<int>w(N,0);vector<int>v(N,0);vector<int>k(N,0);for(int i = 0; i< N ;i++){cin >> w[i];}for(int i = 0; i< N ;i++){cin >> v[i];}for(int i = 0; i< N ;i++){cin >> k[i];}vector<int>dp(C+1,0);for(int i = 0;i < N;i++){for(int j = C;j >= w[i];j--){ //这里忘记考虑01背包要从后往前for(int kk = 1;kk <= k[i];kk++){//这里忘记考虑 =的情况if(j >= kk * w[i])dp[j] = max(dp[j],dp[j - kk * w[i]] + kk * v[i]);}}}cout << dp[C] << endl;return 0;
}
这篇关于代码随想录算法训练营第四十六天的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!