@ 代码随想录算法训练营第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;
}

题目总结

多重背包问题。