DP：segment string

Segment a long string into a set of valid words using a dictionary. Return the maximum number of the subwords.

此题出自facebook面试题。

方法一：套用矩阵连乘积模型。复杂度O(N^3)

int segmentString(string str, set<string> dict)
{ // O(N^3)
    int len = str.length();
    vector<vector<int> > f(len, vector<int>(len, 0));
    for (int k = 0; k < len; ++k)
    {
        for (int i = 0; i < (len - k); ++i)
        {
            int j = i + k;
            if (dict.find(str.substr(i, k + 1)) != dict.end())
            {
                f[i][j] = 1;
            }
            for (int t = i; t < j; ++t)
            {
                if (f[i][t] && f[t+1][j])
                {
                    f[i][j] = max(f[i][j], f[i][t] + f[t+1][j]);
                }
            }
        }
    }

    return f[0][len-1];
}

套用最长上升子序列：复杂度O(N^2)

int segmentString2(string str, set<string> dict)
{
    int len = str.length();
    vector<int> f(len, 0);
    for (int i = 0; i < len; ++i)
    {
        for (int j = i-1; j >= 0; --j)
        {
            if (dict.find(str.substr(j + 1, i)) != dict.end() &&
                f[j])
            {
                f[i] = max(f[i], f[j] + 1);
            }
        }
    }
    return f[len - 1];
}