长沙网页网站制作,济南智能网站建设电话,北京建设教育协会的网站,杭州网站网站建设代码随想录算法训练营第四十六天| 139.单词拆分、卡码网第56题 139.单词拆分卡码网第56题 139.单词拆分 题目链接 文章讲解 class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {int bagSize s.size(), n wordDict.size();vectorboo… 代码随想录算法训练营第四十六天| 139.单词拆分、卡码网第56题 139.单词拆分卡码网第56题 139.单词拆分 题目链接 文章讲解 class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {int bagSize s.size(), n wordDict.size();vectorbool dp(bagSize 1, false);dp[0] true;for (int i 1; i bagSize; i) {for (int j 0; j n; j) {int wordSize wordDict[j].size();if (i wordSize) continue;if (!dp[i - wordSize]) continue;string sub s.substr(i - wordSize, wordSize);if (wordDict[j].compare(sub) 0)dp[i] true;}}return dp[bagSize];}
};卡码网第56题 题目链接 文章讲解 #includebits/stdc.h
using namespace std;
int c, n;
void slove() {vectorint w(n);vectorint v(n);vectorint k(n);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];// 定义dp数组并初始化vectorint dp(c 1, 0);// 遍历for (int i 0; i n; i) {for (int j c; j w[i]; j--) {for (int l 1; l k[i] (j - l * w[i]) 0; l) {dp[j] max(dp[j], dp[j - l * w[i]] l * v[i]);}}}cout dp[c] endl;
}
int main() {while (cin c n) slove();return 0;
}
