旅游社做的最好的网站推广业务

题目：

题解：

一种可行的dp做法是基于完全背包问题，将s看成是一个背包，wordDict看作是物品，然后往s中放入物品判断最终是否可以变为给定的s即可。这道题和上一题都用到了在dp如何枚举连续子串和状态表示：枚举右端点在这过程中枚举所有合理的左端点所有的区间即为合法的连续子串。

bool wordBreak(string s, vector<string>& wordDict) {set<string> se(wordDict.begin(),wordDict.end());int dp[305]={0};dp[0]=1;for(int i=1;i<=s.size();i++){for(int j=0;j<i;j++){if(se.find(s.substr(j,i-j))!=se.end()&&dp[j]){dp[i]=1;}}}return dp[s.size()];}

题后反思：

本题是左闭右开的连续子串枚举，根据题目的递推式将dp[0]=1;