#牛客堂直播视频#经典动态规划题目大串讲（2015.8.5）

预习课程：http://www.nowcoder.com/discuss/1820，即经典算法题精讲（八）-从斐波那契数列学习矩阵乘法的优化技巧、从暴力递归到动态规划

【本期题目】

题目在线练习地址：http://www.nowcoder.com/test/123743/summary

1、字符串的交错组成

【题目】

给定三个字符串str1、str2和aim。如果aim包含且仅包含来自str1和str2的所有字符，而且在aim中属于str1的字符之间保持原来在str1中的顺序，属于str2的字符之间保持原来在str2中的顺序，那么称aim是str1和str2的交错组成。实现一个函数，判断aim是否是str1和str2交错组成。

【举例】

str1=“AB”，str2=“12”。那么“AB12”、“A1B2”、“A12B”、“1A2B”和“1AB2”等等都是str1和str2交错组成。

2、表达式得到期望结果的组成种数

【题目】

给定一个只由0(假)、1(真)、&(逻辑与)、|(逻辑或)和^(异或)五种字符组成的字符串express，再给定一个布尔值desired。返回express能有多少种组合方式，可以达到desired的结果。

【举例】

express=“1^0|0|1”，desired=false。

只有1^((0|0)|1)和1^(0|(0|1))的组合可以得到false。返回2。

express=“1”，desired=false。

没有组合可以得到false。返回0。

3、排成一条线的纸牌博弈问题

【题目】

给定一个整型数组arr，代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。

【举例】

arr=[1,2,100,4]。

开始时玩家A只能拿走1或4。如果玩家A拿走1，则排列变为[2,100,4]，接下来玩家B可以拿走2或4，然后继续轮到玩家A。如果开始时玩家A拿走4，则排列变为[1,2,100]，接下来玩家B可以拿走1或100，然后继续轮到玩家A。玩家A作为绝顶聪明的人不会先拿4，因为拿了4之后玩家B将拿走100。所以玩家A会先拿1，让排列变为[2,100,4]，接下来玩家B不管怎么选，100都会被玩家A拿走。玩家A会获胜，分数为101。所以返回101。

arr=[1,100,2]。

开始时玩家A不管拿1还是2，玩家B作为绝顶聪明的人，都会把100拿走。玩家B会获胜，分数为100。所以返回100。

4、字符串匹配问题

【题目】

给定字符串str，其中绝对不含有字符’.’和’*’。再给定字符串exp，其中可以含有’.’或’*’，’*’字符不能是exp的首字符，并且任意两个’*’字符不相邻。exp中的’.’代表任何一个字符，exp中的’*’表示’*’的前一个字符可以有0个或者多个。请写一个函数，判断str是否能被exp匹配。

【举例】

str=“abc”，exp=“abc”。返回true。

str=“abc”，exp=“a.c”。exp中单个’.’可以代表任意字符，所以返回true。

str=“abcd”，exp=“.*”。exp中’*’的前一个字符是’.’，所以可表示任意数量的’.’字符，所以当exp是“....”时与“abcd”匹配，所以返回true。

str=“”，exp=“..*”。exp中’*’的前一个字符是’.’，可表示任意数量的’.’字符，但是”.*”之前还有一个’.’字符，该字符不受‘*’的影响，所以str起码得有一个字符才能被exp匹配。所以返回false。

注：下面回帖给出了源代码供参考。

【分享嘉宾介绍】