放牧代码和思想
专注自然语言处理、机器学习算法
    时间有限,只有GitHub上的issue能及时处理,大约每周末一次。另外,不要叫我楼主,谢谢。

Qualification Round 2009 Problem C. Welcome to Code Jam DP算法实现

原题: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算法实现

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机