如何选择网站改版公司,pw域名网站,开发微信小程序收费,开源oa系统单词拆分 这道题最后是判断能否组成#xff0c;很像回溯法的问题形式#xff0c;和分割回文串那道题比较类似#xff0c;所以是可以用回溯法解决的#xff0c;但是回溯法需要使用记忆化递归来避免超时。
class Solution{
public:bool backtracking(const string s, const …单词拆分 这道题最后是判断能否组成很像回溯法的问题形式和分割回文串那道题比较类似所以是可以用回溯法解决的但是回溯法需要使用记忆化递归来避免超时。
class Solution{
public:bool backtracking(const string s, const unordered_setstring wordSet, vectorbool memory, int startIndex){if(startIndex s.size()){return true;}// 如果当前位置的memory数组已经更新直接用memory的结果不必再一次计算if(!memory[startIndex]) return memory[startIndex];for(int i startIndex; i s.size(); i) {string word s.substr(startIndex, i - startIndex 1);if(wordSet.find(word) ! wordSet.end() backtracking(s, wordSet, memory, i 1)){return true;}}// startIndex位置开始的字符串无法由给定的字符串组成记录下来memory[startIndex] false; return false;}bool wordBreak(string s, vectorstring wordDict) {unordered_setstring wordSet(wordDict.begin(), wordDict.end());vectorbool memory(s.size(), 1);return backtracking(s, wordSet, memory, 0);}
};动态规划方法
因为给定的字符串可以重复使用所以是完全背包。 dp[i]长度为 i 的字符串如果可以被拆分成给定的那些字符串那么dp[i] true。 递推公式遍历小于 i 的整数 j如果dp[j] true说明在下标j - 1之前的字符串已经符合要求同时再满足 [j, i) 的字符串可以在给定数组中找到那么就可以给 dp[i] 赋值 true。 遍历顺序匹配字符串是要限制顺序的所以应该先背包后物品。
class Solution{
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring wordSet(wordDict.begin(), wordDict.end());vectorbool dp(s.size() 1, false);dp[0] true; // 为了递推能够有效地进行for(int i 1; i s.size(); i) {for(int j 0; j i; j) { // 由于涉及到字符串的索引同时这里i是长度j是下标循环结束的判断条件应该自己模拟一下再决定string word s.substr(j, i - j);if(dp[j] wordSet.find(word) ! wordSet.end()){ // 两项都满足dp[i] true;}}}return dp[s.size()];}
};多重背包理论基础 多重背包物品的数目是有限个我们在遍历的过程中就需要针对某物品考虑到底选几个的问题。方法就是将有多个的物品拆开这样每一个物品又仅有一个了多重背包就转化为了01背包。但是这样操作容易超时可以将遍历物品数目的循环加入到dp数组递推中。
#include bits/stdc.h
using namespace std;
int main() {int bagSize, n;while(cin bagSize n) {vectorint weight(n, 0);vectorint value(n, 0);vectorint nums(n, 0);for(int i 0; i n; i) cin weight[i];for(int i 0; i n; i) cin value[i];for(int i 0; i n; i) cin nums[i];vectorint dp(bagSize 1, 0);for(int i 0; i n; i) {for(int j bagSize; j weight[i]; j--) {for(int k 1; k nums[i] k * weight[i] j; k) {dp[j] max(dp[j], dp[j - k * weight[i]] k * value[i]);}}}cout dp[bagSize] endl;}
}
