码农场原题：https://code.google.com/codejam/contest/90101/dashboard#s=p2&a=2
自己还是太弱了，这题目折腾一下午无解，搜索到一个江湖郎中的解法结果过不了large。仔细看了Contest Analysis才知道要用DP，现在将Contest Analysis简要地翻译一下，以备不时之需。
设T(i)为用例的前i个字符构成的字串，设W(j)为 string = "welcome to code jam" 的前j个字符构成的字串，Dp[i,j]表示这样一个子问题：用T(i)匹配W(j)能匹配多少次。很明显Dp[strlen(test),19]就是题目最终的答案。
问题归结于求Dp[i,j]，但是我们不能直接求出Dp[i,j]，要求Dp[i,j]，必须知道Dp[i-1,j]和Dp[i-1,j-1]才行，原因如下：
用Dp[i,4]做个例子，Dp[i,4]表示test的前i个字符能匹配多少次welc，那么Dp[i+1,4]怎么求呢？Dp[i+1,4]表示字串多加了一个字符：
如果这个字符不等于welc的c的话，那么加了这个字符也不影响匹配次数,Dp[i+1,4] = Dp[i,4]。
如果这个字符等于c的话，那么加了这个字符等于在原来的匹配数上多了新的匹配次数。新的匹配方式等于Dp[i,3]对应的匹配字串加上新加上的字符c，所以Dp[i+1,4] = Dp[i,4]+Dp[i,3]
于是要从Dp[1,1]开始构造整个Dp数组，第一步是推出所有的Dp[i,1]，这是最简单的：
如果test的第1个字符等于w的话，Dp[1,1]就为1，否则就为0。
如果test的第2个字符等于w的话，Dp[2,1]就为Dp[1,1] + 1，否则就为Dp[1,1]。(没有Dp[1,0]或者说Dp[1,0]=1)
……
第二步是推导所有的Dp[i,j]，有了Dp[i,1]这就简单了，我们只要对j进行一次遍历（这次遍历从2开始）:
如果test的第2个字符等于string[2]的话，Dp[2,2]就为Dp[2,1]+Dp[1,1]，否则就为Dp[2,1]。
如果test的第2个字符等于string[3]的话，Dp[2,3]就为Dp[2,2]+Dp[1,2]，否则就为Dp[2,2]。
……
如果使用C系列语言的话，上面的Dp下标都要从0开始。
我的解决方案：
#include <iostream>
#include <string>
#include <iomanip>
using namespace std;
const static string words = "welcome to code jam";
const static int lw = words.length(); // 19
int lt = 0; // text用例的长度
unsigned int dp[500][19];
//************************************
// Method: solve
// FullName: solve
// Access: public
// Returns: unsigned int text前li个字母匹配words前lj + 1个字母的可能匹配数
// Qualifier:
// Parameter: const string & text 用例
// Parameter: unsigned int li text前li + 1个字母
// Parameter: unsigned int lj words前lj + 1个字母
//************************************
unsigned int solve(const string& text, unsigned int li, unsigned int lj)
{
if (text[0] == words[0]) // 'w'
{
dp[0][0] = 1;
}
for (int i = 1; i < lt; i++)
{
// 推出dp[i][0] 作为初始化
if (text[i] == words[0]) // 'w'
{
dp[i][0] = dp[i - 1][0] + 1; // 如果子字串最后一个字母等于w，则多1种选择
}
else
{
dp[i][0] = dp[i - 1][0]; // 没得选，加了一个字母等于没加
}
// 推出dp[i][1]...dp[i][18]
for (int j = 1; j < lw; j++)
{
if (text[i] == words[j])
{
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
}
else
{
dp[i][j] = dp[i - 1][j];
}
dp[i][j] %= 10000;
}
}
return dp[li][lj];
}
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
int nCases = 0;
cin >> nCases;
cin.get();
for (int i = 0; i < nCases; i++)
{
string text;
getline(cin ,text);
memset(dp, 0, sizeof(dp));
cout << "Case #" << i + 1 << ": ";
lt = text.length();
cout << setfill('0') << setw(4) << solve(text, lt - 1, 19 - 1) << endl;
}
fclose(stdin);
fclose(stdout);
/*system("out.txt");*/
return 0;
}
///////////////////////////End Sub//////////////////////////////////
做完这个题目感觉非常失落，自己的算法还处于很幼稚的阶段。几大经典算法都不明白，看来得好好补一补。
知识共享署名-非商业性使用-相同方式共享：码农场 » Qualification Round 2009 Problem C. Welcome to Code Jam DP算法实现