@ 代码随想录算法训练营第8周（C语言）|Day51（动态规划）

本文主要是介绍@ 代码随想录算法训练营第8周（C语言）|Day51（动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

@ 代码随想录算法训练营第8周（C语言）|Day51（动态规划）

Day51、动态规划（包含题目 139.单词拆分 ）

139.单词拆分

题目描述

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

题目解答

char* substring(int j,int i,char*s){int len=i-j;char*ret=(char*)malloc(sizeof(char)*(len+1));for(int z=0;z<len;z++ ){ret[z]=s[++j];}ret[len]='\0';return ret;
}
bool comparestring(char **wordDict,char*s,int wordDictSize){for(int i=0;i<wordDictSize;i++){if(strcmp(wordDict[i],s)==0){return true;}}return false;
}bool wordBreak(char* s, char** wordDict, int wordDictSize) {int len=strlen(s);int dp[len+1];char s1[len+1];for(int i=1,j=0;i<=len;i++){s1[i]=s[j++];dp[j]=0;}dp[0]=1;for(int i=1;i<=len;i++){for(int j=0;j<i;j++){char*ret=substring(j,i,s1);if(comparestring(wordDict,ret,wordDictSize)&&dp[j]==1){dp[i]=1;}}}if(dp[len]==1){return true;}return false;
}

题目总结

多重背包问题。

这篇关于@ 代码随想录算法训练营第8周（C语言）|Day51（动态规划）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---