2016算法课程设计题目12个

wordword/word1、打包行李宰勋每次不到旅行前日都绝不会打包行李，今天也是到了登机的前一天才坐下来开始打包的。航空公司规定每人只能携带1件行李，而宰勋要带的东西比拟多，1个行李箱肯定是不够的。下面的目录列出了他想要带的每件物品的体积和必要程度。物品笔记本电脑相机XBOX365咖啡研磨机哑铃百科全书体积4264210必要程度7106754因行李箱的空间有限，所以能够放进去的物品总体积不能超过w。编写程序计算出必要程度总和最大的物品目录。示例输入值：2610laptop47camera210xbox66grinder47dumbbell25encyclopedia104617laptop47camera210xbox66grinder47dumbbell25encyclopedia104示例输出值：243laptopcameragrinder304laptopcameraxboxgrinder2、计算第k个答案摩尔斯电码字典在没有的时代，摩尔斯电码是无线电传输领域中的一种常用代码。电码以短信号〔短点，o〕和长信号〔长点，-〕的不同组合表示各种文字。例如：o—表示英文字母J，而—表示英文字母M。假设有一本以n个长点和m〔n、m<=100〕个短点组成的、包含所有信号的字典。例如：n=m=2，就会包含如下信号。--oo-o-o-oo-o--oo-o-oo--这些信号已按照字典顺序排列好了。-的ASKII码是45，而o的ASCII码是111。因此，按照字典顺序，-在前，o在后。给定n和m时，编写代码计算出此字典的第k〔k<=1,000,000,000,000〕个信号。例如：上述字典的第四个信号是o--o。3、剑客决斗在路易十三和红衣主教黎塞留当权的时代，发生了一场决斗。n个人站成一个圈，依次抽签。抽中的人和他右边的人决斗，负者出圈。这场决斗的最终结果关键取决于决斗的顺序。现书籍任意两决斗中谁能胜出的信息，但“A赢了B〞这种关系没有传递性。例如，A比B强，B比C强，C比A强。如果A和B先决斗，C最终会赢，但如果B和C决斗在先，如此最后A会赢。显然，他们三人中的第一场决斗直接影响最终结果。假设现在n个人围成一个圈，按顺序编上编号1~n。一共进展n-1场决斗。第一场，其中一人〔设i号〕和他右边的人〔即i+1号，假如i=n，其右边人如此为1号〕。负者被淘汰出圈外，由他旁边的人补上他的位置。n个人之间的强弱关系〔即任意两个人之间输赢关系〕。如果存在一种抽签方式使第k个人可能胜出，如此我们说第k人有可能胜出，我们的任务是根据n个人的强弱关系，判断可能胜出的人数。输入第一行是一个整数N(1<=N<=20)表示测试数据的组数。第二行是一个整数n表示决斗的总人数。(2<=n<=500)随后的n行是一个n行n列的矩阵，矩阵中的第i行第j列如果为1表示第i个人与第j个人决斗时第i个人会胜出，为0如此表示第i个人与第j个人决斗时第i个人会失败。输出对于每组测试数据，输出可能胜出的人数，每组输出占一行样例输例输出34、第k个最大递增子序列某个整数序列中，去掉0个以上的数字后，剩余的局部就是原序列的子序列。例如，{7,4,9}、{10,4}、{10,9}等是{10,7,4,9}的子序列。而序列{10,4,7}具有不同于原序列的排列顺序，因而不属于{10,7,4,9}的子序列。严格递增的子序列称为递增子序列。序列的递增子序列中，最长的序列称为最大递增子序列〔LIS〕。例如：{5,20,21,22,8,9,10}的最大递增子序列是{5,8,9,10}。〔不唯一〕给出以不同数字组成〔无重复数字〕的序列时，请编写程序，计算此序列的LIS中按照字典序排在第k个位置的LIS。输入第一行输入测试用例的个数C〔C<=50〕。各测试用例的第一行输入序列中元素的个数n〔1<=n<=500〕和k〔1<=k<=2*109〕。第二行输入序列的n个元素。各元素是大于等于1而小于等于100,000的整数，且同一数字只出现1次。可以假设序列的LIS至少有k个。输出每个测试用例在第一行输出LIS的长度l，第二行以l个整数输出第k个LIS。示例输入：3865164328784214365878256781234示例输出：314841368456785、津巴布韦由于计划经济失败，津巴布韦称为世界上通胀率最高的国家。这里的物价即使在一天中也会持续上涨，所以必须实时更新物品价格。例如：1个鸡蛋的价格为35亿津巴布韦元，所以超市做了每位数字的活动标价牌。钟旭在穆加贝超市打工，有一天遇到了一位比拟麻烦的客人。这位客人要退回刚刚买走的鸡蛋，但是他不仅丢失了发票，而且连购置鸡蛋的数量也记不清了。鸡蛋价格已经在此期间上涨了1次，所以广告牌上已经写上新的价格。辛亏钟旭还记得如下两件事情。1〕最近一次价格上涨的时候，钟旭只是交换了塑料板的顺序。也就是说，没有添加其他塑料板，也没有去掉过广告牌中的塑料板。2〕看到最近一次上涨的价格时，钟旭心里曾经想过，“哇，这些钱刚好能购置m个糖果〞。所以，最后的鸡蛋价格是m的倍数。〔因为糖果的价格已经上涨，所以不能计算出鸡蛋的价格了〕。输入第一行输入测试用例的个数C〔C<=50〕。之后的C行里面每行输入两个自然数e和m〔1<=e<=1014，2<=m<=20〕。当前鸡蛋的价格不能以0开始，但是之前的价格可以以0开始。输出每个测试用例在1行内输出可能的价格个数除以1000000007的余数。示例输入值：4321312334222示例输出值50211033示例输入输出值的说明第一个示例输入值：以前鸡蛋的价格可能是123元、132元、213元、231元、312元。第二个示例输入值：无论怎样重新排列123元的数字，结果都会比123元大，故无解。第三个示例输入值：224元和242元是可能的价格。第四个示例输入值：鸡蛋简直太贵了。6、完全覆盖有一天acmj在玩一种游戏用2*1或1*2的骨牌把m*n的棋盘完全覆盖。但他感觉把棋盘完全覆盖有点简单，他想能不能把完全覆盖的种数求出来？由于游戏难度增加他自己已经没法解决了，于是他希望大家能用程序来帮他把问题解决了。输入有多组数据。每组数据占一行，有两个正整数n〔0<n<12〕,m(0<m<12)。当n，m等于0时输入完毕输出每组数据输出占一行，输出完全覆盖的种数。样例输入22232421141100样例输出235144512057、逃狱的汉尼拔博士杀人狂魔汉尼拔博士逃狱了。通缉令发布后，大量军警出动并实施全天候追捕，不过狡猾的汉尼拔博士并没有落网。过了d日后，束手无策的警察们拜访了有着“编程天才〞之称的查理教授。查理教授对汉尼拔博士留在监狱的笔记本进展分析后，做出了如下假设。1〕汉尼拔博士为了避开检查，只走山路；2〕汉尼拔博士越狱当天选择了与监狱相邻的村子之一作为藏身之处；3〕汉尼拔博士为了逃避追捕，每天往一个相邻的村子逃窜。为了验证假设，教授找到了与监狱所在村子以山路连接的n个村子的地图。汉尼拔博士会按照此假设行动，而且会随机选择一个备选的村子。编写程序计算d日后汉尼拔博士在各个村子的概率。例如监狱在第三个村子，逃狱后的汉尼拔博士会在0、1、2、4、5中任意选择一个村子藏身。因此，1天后汉尼拔博士藏在第0号村子的概率是1/5，两天后藏在第1号村子的概率是1/15。输入第一行输入测试用例的个数C〔1≤C≤50〕。之后各行输入地图上显示的村子个数N〔2≤N≤50〕和逃狱后经过的天数D〔1≤D≤100〕，以与监狱所在村子的P〔0≤P<N〕，村子的由0到N-1的数字组成。之后N行里各输入N个整数，形成一个序列A。第i行j列的数值A[i][j]如果等于1，就表示从第i号村子到第j号村子有山路可走；如果是0，如此表示无路可通。接下来的一行输入要计算概率的村子的个数T〔0≤T<N〕，最后一行以整数型输入要计算概率的村子的Q〔0≤Q<N〕。如果一个村子与另一个村子相连，那么相反的路径也必定存在。可假设一个村子连接到自身的路径不存在。输出每个测试用例以T个实数输出汉尼拔博士可能藏匿的概率。存在小于10-7的绝对/相对误差的答案将被视为正确答案。示例输入值252001110100011000010000010003024823011100001001000010010000111011000001001100010001000010000000110043126示例输出值8、回转寿司algospot内部举行的解题投注比赛中，积累的罚金实在太多，于是运营团队决定举行一次会餐，地点选择在回转寿司店。来到回转寿司店的运营团队并没有急于品尝寿司，而是开了一个“策略〞会议。寿司店里共有n种菜品，团队对各个菜品标上了如下等级。寿司种类鸡蛋三文鱼鳗鱼金枪鱼牛排炸鸡价格25003000400050001000015000等级791012201运营团队要在不超过预算的情况下吃到等级总和最大的菜品。假设可供购置的寿司不限量，那么能吃到的最大等级之和是多少呢？输入第一行输入测试用例的个数C〔1<=C<=5〕。各测试用例的第一行输入寿司的种类n〔1<=n<=20〕和团队的总预算m〔1<=m<=109〕。之后的n行中，每行输入一种寿司的价格和等级。价格是2000以下的整数，但必须是100的倍数。等级是20以下的自然数。输出每个测试用例在1行内输出可能的最大等级之和。示例输入值2610000250073000940001050001210000201500016543975612250073000940001050001210000201500019、龙曲线龙曲线是以简单的数学规如此画出一种曲线，它具有以下形态。曲线从一个简单的线段起始，按照一定规如此变换此线段完成整个曲线。每形成一次变换称为“完成了一次变换代〞，而每完成一代，曲线会进化到更复杂的形式。像这种“放大其一小局部的形状时，表现出与整个形状极为相似构造的图形〞，就是分形。画出龙曲线的方法暂且就称为龙曲线字符串吧！龙曲线字符串由X、Y、F、+、-组成。那么，要画出龙曲线就从一个点起始画出如下曲线即可。F：向前方移动一格并画线。+：向左旋转90度。-：向右旋转90度。X、Y：忽略。画出第0代龙曲线的字符串是FX。从下一代开始，按照如下方式利用前一代字符串进展字符替换，从而获得当前一代的龙曲线字符串。X->X+YFY->FX+Y根据上面的替换式，就有如下的1、2代龙曲线字符串。第一代：FX+YF第二代：FX+YF+FX-YF我们想要求出第n代龙曲线字符串。不过，考虑到答案有可能很长，所以只想计算出第p个字符起始长度为l个字符的字符串。请编写程序实现这种功能。输入第一行输入测试用例的个数C〔C<=50〕。各测试用例的第一行分别输入3个整数，即龙曲线的世代n〔0<=n<=50〕、p以与l〔1<=p<=1000000000、1<=l<=50〕。第n代龙曲线字符串的长度可假设成总是大于等于p+l的数值。输出每个测试用例在1行内输出第n代龙曲线字符串的第p个字符开始，输出l个字符。示例输入40121152654276485347530示例输出FXFY+YF+FX-YFX-YF-FX+YF+FX-YF-FX+YF-FX-YF-10、通配符通配符在很多操作系统中只用局部文件名指定文件。这些加有通配符的字符串就是通配符X式，这种X式与文件名类似，但常常是包含特殊字符“*〞或“？〞的字符串。从通配符X式的第一个字符开始与文件名比拟，如果所有字符都一致，那么通配符X式与文件名相对应。通配符X式中的“？〞字符可以充当任何一个字符，而“*〞字符可以充当长度大于等于0的任一字符串。例如，通配符X式he?p可表示help、heap，但不能表示helpp。而通配符X式“*p*〞可表示help、papa，但不能表示hello。下面给定通配符X式和文件名集合，编写程序找出对应于通配符X式的文件名。输入第一行输入测试用例的个数C〔1<=C<=10〕。各测试用例的第一行输入通配符X式W，第二行输入文件名数量n〔1<=n<=50〕。接下来的n行中，每行输入1个文件名。通配符X式由大小写英文字母、数字、*、？组成，文件名由大小写英文字母和数字组成。所有字符串的长度都大于等于1小于等于100，且不包含空格。输出每个测试用例将按照字母顺序每行显示1个对应于通配符X式的文件名。示例输入3he?p3helpheaphelpp*p*3helppapahello*bb*1babbbc示例输出heaphelphelppapababbbc设计通配符匹配算法，其中*号可以匹配任意多个字符，？号可以匹配任意一个字符。例如12345和12*、12*？以与12*4？等都匹配。函数原型为：boolmatch(constchar*str,constchar*strpattern);

分析：利用动态规划来解决。此题类似与LCS问题。假设字符串A[i]代表前i+1个子字符串，B[j]代表前j+1个子字符串，那么A[i]与B[j]是否匹配可以由A[i-1],B[j-1];A[[i-1],B[j];以与A[i]B[j-1]结合当前A[i]与B[j]的字符来确定。

A[i]与B[j]匹配需进展如下判断1、假如(strpattern[j-1]=='?'&&str[i-1]!='\0')或者strpattern[j-1]==str[i-1]，即A[i]与B[j]的最后一个字符必须“一样〞(这里一样是指必须占用一个字符)，如此只需判断A[i-1]和B[j-1]是否匹配；2、假如strpattern[j-1]=='*'，如此只需A[i]和B[j-1]匹配或者A[i-1]和B[j-1]匹配或者A[i-1]和B[j]匹配即可确定A[i]与B[j]匹配.

代码如下：[cpp]

\o"viewplain"viewplain\o"copy"copybool

match_string(const

char*

str,

const

char*

strpattern)

{

int

nStr

=

strlen(str);

int

nPatt

=

strlen(strpattern);

int**

pTable

=

new

int*

[nStr+1];

for(int

k

=

0;

k

<=

nStr;

k++)

{

pTable[k]

=

new

int

[nPatt+1];

memset(pTable[k],0,(nPatt+1)*sizeof(int));

}

if(strpattern[0]

==

'*')

{

for(int

i

=

0;

i

<=

nPatt;

++i)

{

pTable[0][i]

=

1;

}

}

pTable[0][0]=1;

for

(int

j

=

1;

j

<=

nPatt;

++j)

{

for

(int

i

=

1;

i

<=

nStr;

++i)

{

if((strpattern[j-1]

==

'?'

&&

str[i-1]

!=

'\0')

||

strpattern[j-1]==str[i-1]){

pTable[i][j]

=

pTable[i-1][j-1];

}

else

if(strpattern[j-1]

==

'*'){

if(pTable[i][j-1]

==

1

||

pTable[i-1][j]

==

1

||pTable[i-1][j-1]==1)

pTable[i][j]

=

1;

}

}

}

bool

ret

=

(pTable[nStr][nPatt]

==

1

?

true

:

false);

for(int

k

=

0;

k

<=

nStr;

k++)

delete

[]

pTable[k];

delete

pTable;

return

ret;

}

测试代码如下：[html]

\o"viewplain"viewplain\o"copy"copyint

main(int

argc,

char**

argv)

{

if(match_string(argv[1],argv[2]))

{

cout

<<

argv[1]

<<

"

and

"

<<

argv[2]

<<

"

matched!"

<<

endl;

}

else

cout

<<

argv[1]

<<

"

and

"

<<

argv[2]

<<

"

are

not

matched!"

<<

endl;

return

0;

}

1.简述

题目描述：

Str1中可能包含的字符：除了'*'和'?'以外的任意字符。

Str2中可能包含的字符：任意字符。其中，'?'表示匹配任意一个字符，'*'表示匹配任意字符0或者屡次。

给出这样两个字符串，判断Str2是否是Str1的子串，如果是输出第一个匹配到的子串，如果不是，输出"不是子串"。2.分析

对于'?'的处理，只要在匹配的时候将代码由：if(str1[i]==str2[j])改为if(str1[i]==str2[j]||str2[j]=='?')即可。

对于'*'的处理，可以将str2根据其中的'*'分为假如干个片段，然后依次在str1中分别匹配这几个片段即可，而且对于这几个片段分别匹配，如果第k个片段在str1中匹配不到，后面也可以完毕了。这里举例说明一下：对于str1="Ohyear.Totayisweekend!"，str2=*ye*a*e*"，实际上就是在str1中匹配"ye","a","e"这三个片段。

Ohyear.Totayisweekend!

yea

e

yea

e

yea

e

ye

a

e

ye

a

e

ye

a

e

实际上，能够匹配到上面6种情况，按照我们的如果从左到右的匹配每个片段返回的是第一种情况。这里主要分析这种情况的处理，对于所有情况的输出后面再简单说明一下。

首先处理str2，根据'*'分成假如干个局部，然后依次在str1中进展匹配，使用kmp算法即可。这样判断能否匹配或者只找第一个匹配的子串的负责度是O(m+n)3.代码实现

其中利用了kmp算法，为了使用方便，稍微改了下kmp算法的输入参数，即pat字符串的长度不用'\0'确定，用指定参数确定。#include

<iostream>

#include

<deque>

using

namespace

std;

//

KMP算法，pat长度由len_pat指定

void

get_next(const

char

pat[],

int

next[],

int

pat_len)

{

//

int

len

=

strlen(pat);

int

len

=

pat_len;

int

i,j;

next[0]

=

-1;

for(i=1;

i<len;

i++)

{

for(j=next[i-1];

j>=0

&&

pat[i-1]!=pat[j];

j=next[j])

;

if(j<0

||

pat[i-1]!=pat[j])

next[i]

=

0;

else

next[i]

=

j+1;

//

if

(pat[i]==pat[next[i]])

next[i]=next[next[i]];

}

for(int

i=0;

i<len;

i++)

{

if(pat[i]

==

pat[next[i]])

next[i]

=

next[next[i]];

}

}

//

KMP算法，str长度由'\0'判断，pat长度由len_pat指定

int

kmp_next(const

char

text[],

const

char

pat[],

int

pat_len)

{

int

t_length

=

strlen(text);

//

int

p_length

=

strlen(pat);

int

p_length

=

pat_len;

int

t,p;

int*

next

=

new

int[p_length];

get_next(pat,

next,

p_length);

for(t=0,p=0;

t<t_length,p<p_length;

)

{

if(text[t]

==

pat[p])

t++,p++;

else

if(next[p]

==

-1)

//

说明此时p=0，而且pat[0]都匹配不了

t++;

else

p

=

next[p];

}

delete

[]next;

return

t<t_length

?

(t-p_length):-1;

}

//

切分pat的结构

struct

PAT_INFO

{

char*

pat;

int

len;

};

//

可以匹配通配符的KMP，返回第一个匹配子串在str中的下标

void

KMP_WildCard(char*

str,

char*

pat)

{

int

len_str

=

strlen(str);

int

len_pat

=

strlen(pat);

int

i,j;

deque<PAT_INFO>

store;

//

切分pat到store中

PAT_INFO

info;

bool

new_info

=

true;

for(i=0;

i<len_pat;

i++)

{

if(pat[i]

==

'*')

{

if(new_info

==

false)

//

有info需要保存

store.push_back(info);

new_info

=

true;

}

else

{

if(new_info)

{

//

需要新建一个info

info.pat

=

pat

+

i;

info.len

=

1;

new_info

=

false;

}

else

{

//

不需要新建一个info

info.len++;

}

}

}

//

for

//

测试切分结果

/*

while(store.size()

>

0)

{

info

=

store.front();

for(i=0;

i<info.len;

i++)

cout

<<

info.pat[i];

cout

<<

endl;

store.pop_front();

}*/

//

根据切分后的pat序列进展匹配

int

first_index

=

-1;

//

起始的下标

int

last_index

=

0;

//

最后的下标后面的一个位置

int

next_index

=

0;

//

下一次开始匹配的下标

while(store.size())

{

info

=

store.front();

next_index

=

kmp_next(str+next_index,

info.pat,

info.len);

if(next_index

==

-1)

{

//

这个片段没找到，查找任务失败

break;

}

else

{

//

这个片段找到了，继续找

if(first_index

==

-1)

{

//

找到的第一个片段

first_index

=

next_index;

}

last_index

+=

next_index

+

info.len;

next_index

=

last_index;

}

store.pop_front();

//

cout

<<

last_index

<<

endl;

}

if(store.size())

cout

<<

"not

found"

<<

endl;

else

{

for(i=first_index;

i<last_index;

i++)

cout

<<

str[i];

cout

<<

endl;

}

}

int

main()

{

char

*

str

=

"Oh

year.Totay

is

weekend!";

char

*

pat

=

"*ye*a*e*";

cout

<<

"str:

"

<<

str

<<

endl;

cout

<<

"pat:

"

<<

pat

<<

endl;

cout

<<

"res:

";

KMP_WildCard(str,

pat);

system("PAUSE");

return

0;

}

4.所有匹配结果输出

例子：Ohyear.Totayisweekend!

yea

e

yea

e

yea

e

ye

a

e

ye

a

e

ye

a

e

首先是所有结果是什么：如果我们要的是str1匹配到的字符串，那么可见实际上上面6个有3个是重复的，因此对于这种情况，只有得到匹配字符串在str1中的开始index和完毕index，然后对于重复的去掉即可。如果要的是str1匹配到的字符的下标，那么这是不会重复的。

然后说一下匹配方法，根本上与匹配一个的差不多，不过要加上回溯的过程。比如第一次匹配成功后，继续在新的位置匹配最后一个片段，如果成功了就是第二次匹配成功了，否如此就要回溯取在新的位置去匹配倒数第二个片段了，依次类推。直到第一个片段都没法再匹配到，不再回溯了。此外值得注意的是，如果第一次匹配都没成功，就不必回溯了，这种情况下，说明不可能存在匹配结果，因为匹配是从左到右的顺序，都会尽量在左边找到适宜的片段，如果第一次都没成功，假设在第k个片段上匹配失败了，那么再回溯的话，轮到k片段是空间实际上只会与上次一样或者更小，大的空间都匹配不到，小的空间更不用说了。

还有一点值得注意：有的一些博文采用的是用str2中一个字符一个字符的匹配，感觉效率会低，而且也没有片段这个方法中的第一次匹配失败就可以停止的规律，也用不了kmp〔准确的说是表现不出kmp的优势〕。A[i]与B[j]匹配等价于1、A[i-1]与B[j-1]匹配并且(A[i]==B[j]||A[i]==*||(A[i]==’?’&&B[j]!=‘\0’))2、A[i-1]与B[j]匹配并且(A[i]==’*’)3、A[i]与B[j-1]匹配并且(A[i]==’*’||(A[i-1]==’*’&&(A[i]==B[j]||(A[i]==’?’&&B[j]!=‘\0’))))之间任何一个成立字符串匹配问题，给定一串字符串，按照指定规如此对其进展匹配，并将匹配的结果保存至output数组中，多个匹配项用空格间隔，最后一个不需要空格。要求：1.

匹配规如此中包含通配符?和*，其中?表示匹配任意一个字符，*表示匹配任意多个〔>=0〕字符。2.

匹配规如此要求匹配最大的字符子串，例如a*d,匹配abbdd而非abbd,即最大匹配子串。3.

匹配后的输入串不再进展匹配，从当前匹配后的字符串重新匹配其他字符串。

我们先考虑rule是否匹配input某一个前缀的情况的情况相关动态规划算法如下：设状态dp[i][j]为rule[i]与input[j]是否匹配〔true或false〕分别考虑rule[i]==?,*以与普通字符的情况rule[i]='*'时:1.

dp[i][j-1]==true能推出di[i][j]==true但是dp[i][j-1]==false不能推出dp[i][j]==false(考虑rule[0...i]=abc*和input[0...j-1]=ab且input[j]=c。所以不能用dp[i][j-1]2.

应该用dp[i-1][j]和dp[i-1][j-1]。其实是一样的，因为dp[i-1][k]=true即可推出dp[i][j]=true〔其中0<=k<=j〕。否如此就是false。即dp[i][j]与dp[i-1][k]的或等价。rule[i]='?'时:1.

dp[i][j-1]和dp[i-1][j]都不能推断出dp[i][j]。比如dp[i][j-1]=ture时，如果rule[0…i]都是普通字符，如此明显dp[i][j]=false。但是如果rule[0…i]=*时，如此明显dp[i][j]也是true。同理dp[i-1][j]也不能〔分别考虑rule[0…i-1]是普通字符串和是*的情况〕2.

dp[i-1][j-1]与dp[i][j]是无条件等价的，可以分别考虑dp[i-1][j-1]=true或false的情况。

rule[i]为普通字符时:1．

同rule[i]==’?’一样，无法通过dp[i][j-1]和dp[i-1][j]推断出dp[i][j]2．

(dp[i-1][j-1]&&rule[i]==input[j])与dp[i][j]等价。

设rule，input都从1开始：初始化：dp[0][1….j_len]=flasedp[1…i_len][0]=falsedp[0][0]=true.

动态规划递归式为：1.

rule[i]==’*’:dp[i][j]=(dp[i-1][k]的或，k=0…j)2.

rule[i]!=’*’:dp[i][j]=(dp[i-1][j-1]&&(rule[i]==input[j]||rule[i]=’?’))

从该题得到的思考：动态规划的递归式需要是充分必要条件：

充分：即当满足递归式时，一定能给出正确的结果。在该题中，即当rule=’?’且dp[i-1][j-1]=ture时dp[i][j]一定是ture。

必要性：所有结果都能通过该递归式得到，不能有遗漏。即完备性。动态规划的完备性其实很好证明，比如在此题中，只要考虑rule[i]的3种可能取值和将dp[i][j]表填满就行了。即rule=’?’时，虽然dp[i][j-1]和dp[i-1][j]不能用，但是可以通过dp[i-1][j-1]就可以得出结果，加上初始化的值，就可以得出整个dp表的值。

以上是快速判断rule是否与input匹配的算法。但是题目其实是要知道rule是否与input的某一子段匹配，一个方法就是遍历以input[0]到input[len]开头的所有子串。即在外面再加一层循环。复杂度是〔rule_len〕*(input_len)^2。

但是其实改一下状态设置就可以直接用动态规划解决。

相关动态规划算法如下：设状态dp[i][j]为rule[0…i]匹配以input[j]结尾的input字符串的最大长度分别考虑rule[i]==?,*以与普通字符的情况如上rule[i]='*'时:

假如dp[i-1][k]!=-1,如此dp[i-1][k]+j-k就是dp[i][j]当然，得从众多的k中选一个最大的，即dp[i][j]=max{dp[i-1][k]+j-k,0<=k<=j且dp[i-1][k]!=-1}

rule[i]='?'时:rule[i]为普通字符时:

rule[i]必须与input[j]对应上，而且要想将rule[0…i]都匹配上，dp[i-1][j-1]就不能等于-1，即必须匹配。即dp[i-1][j-1]!=1且rule[i]与input[j]匹配〔rule[i]==input[j]||rule[i]=’?’〕

设rule，input都从1开始：初始化：dp[0][1….j_len]=0dp[1…i_len][0]=-1dp[0][0]=0

动态规划递归式为：3.

rule[i]==’*’:dp[i][j]=max(dp[i-1][k]+j-k)0<=k<=j且dp[i-1][k]!=-1)4.

rule[i]!=’*’:dp[i][j]=(dp[i-1][j-1]!=-1&&(rule[i]==input[j]||rule[i]=’?’))?dp[i-1][j-1]+1:-1;

其中初始化的dp[0][1….j_len]=0很重要。例如rule=〞n〞，input=〞nsn〞。当n匹配到nsn的第二个n时，就是求dp[1][3]时，要看dp[0][2]，如果dp[0][2]=-1,如此意味着rule中n字母之前的就已经不匹配，所以该n也不能匹配。但是很明显，n之前没有字母需要匹配，即要把dp[0][0…len]这种特殊情况摘出来。即不需要考虑之前是否匹配〔因为不需要〕，从新开始匹配。

11、量化量化过程将宽X围的数值表示为小X围的近似值，从而达到有损压缩的目的。例如：16位的JPG文件转换成4色的GIF文件，就是把RGB颜色空间的颜色量化成4种颜色的过程。还有，把身高为161、164、178、184的4名学生表示成“160-169阶段的2名，170-179阶段的1名、180以上阶段的1名〞的方式也是量化。现要把小于1000的自然数组成的序列量化成s个自然数组成的序列。量化的方法其实很多，例如，只用两个数表示序列{12345678910}，就可以表示成{3333377777}。或还可以用{111111010101010}的形式表示。那么，各数值误差平方之和最小的量化结果是多少呢？比如，把序列{12345}量化成{22333}，各数值量化后的误差是-1、0、0、1、2。那么，误差平方之和是1+0+0+1+4=6。但是，如果量化成{22344}，那么误差平方之和是1+0+1+0+1=3。接下来请编写程序，求用s个数值量化给定序列后，误差平方之和的最小值。输入第一行输入测试用例的个数C〔1<=C<=50〕。各测试用例的第一行输入序列的长度n〔1<=n<=100〕，以与可使用的数值个数s〔1<=s<=10〕。第二行输入序列的n个整数，且序列的所有数值是1000以下的自然数。输出每个测试用例将在1行内输出用s个数值量化给定序列时产生的最小误差平方之和。示例输入值2103333123222193174475548979028906777示例输出值065112、探寻宝藏传说HMH大沙漠中有一个M*N迷宫，里面藏有许多宝物。某天，Dr.Kong找到了迷宫的地图，他发现迷宫内处处有宝物，最珍贵的宝物就藏在右下角，迷宫的进出口在左上角。当然，迷宫中的通路不是平坦的，到处都是陷阱。Dr.Kong决定让他的机器人卡多去探险。但机器人卡多从左上角走到右下角时，只会向下走或者向右走。从右下角往回走到左上角时，只会向上走或者向左走，而且卡多不走回头路。〔即：一个点最多经过一次〕。