动态编程-分词

动态编程-分词

您的代码实际上是错误的。要使代码失败，请尝试输入“ likeman”

请注意，函数

searchSentence

0或1 有两个不同的返回值。因此，如果

r

使用0 初始化数组，则不能保证它为新状态

r[x][y] =0

。用一些不可能的值（例如-1或2）初始化r数组，然后再次测试。现在，您可以轻松确认是否

r[qbegin][qend] !=-1

已经检查了此状态，因此您可以

r[qbegin][qend]

从此处 返回

更新的代码：

#include <iostream>#include <string.h>using namespace std;int r[100][100];  //To Store the calculated valuesbool searchWord(char q[], char D[][20], int start, int end){    cout << "In Search Word Loop with " << start << " " << end << endl;    char temp[end - start + 1];    int j = 0;    for (int i = start; i <= end ; ++i)    {        //cout << "Looping i " << i << endl;        temp[j] = q[i];        j++;    }    temp[j] = '';    //cout << "For Word " << temp << endl;    for (int i = 0; i < 12; ++i)    {        // cout << "Comparing with " << D[i] << endl;        if (!strcmp(temp, D[i]))        { cout << "Found Word" << temp << " " << D[i] << endl; return 1;        }    }    return 0;}bool searchSentence(char q[], char D[][20], int qstart, int qend){    cout << "In Search Sentence Loop" << endl;    if (r[qstart][qend] != -1)    {        cout << "DP Helped!!!" << endl;        return r[qstart][qend];    }    if (qstart == qend)    {        if (searchWord(q, D, qstart, qstart)) return 1;        else return 0;    }    if (qstart > qend) return 1;    int i;    for (i = qstart; i <= qend; i++)    {        if (searchWord(q, D, qstart, i))        { r[i + 1][qend] = searchSentence(q, D, i + 1, qend); if (r[i + 1][qend] == 1) return 1;        }    }    return 0;}int main(){    char D[20][20] = { "i", "like", "sam", "sung", "samsung", "mobile", "ice", "cream", "icecream", "man", "go", "mango"};    char q[100] = "ilike";    int index = 0; char ch;    ch = q[0];    memset(r, -1, sizeof(r));    while (ch != '')    {        index++;        ch = q[index];    }    if (searchSentence(q, D, 0, index - 1))    cout << "Yes" << endl;    else cout << "No" << endl;}

PS：有一些多余的代码行，但是我没有更改它们，而是在函数的字符数组temp的末尾添加了一个空字符

searchWord