ACM动态规划总结动态规划经典题傻瓜式讲解

动态规划

4星 · 超过85%的资源需积分: 10 185 浏览量更新于2023-07-19 5 收藏 460KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

Pku acm 1163 the Triangle 动态规划题目总结(一)

题目：

对于一个有数字组成的二叉树，求由叶子到根的一条路径，使数字和最大，如：



 



!!

!" "

这个是经典的动态规划，也是最最基础、最最简单的动态规划，典型的多段图。思路

就是建立一个数组，由下向上动态规划，保存页子节点到当前节点的最大值，# 核心代

码如下：

for$int% &'&%%()

for$int*&*+&*,,()

该句是整个动态规划的核心

-.-*./max$-,.-*.0-,.-*,.(,-.-*.&

带有详细注释的代码可以在 233!获得

Pku acm 1579 Function Run Fun 动态规划题目总结(二)

 "4 

53%3#62$00(

6+++02$00(3

6' ' ' 02$00(32$ 0 0 (

6++02$00(32$00%(,2$0%0%(%2$0

%0(

2332$%00(,2$%0%0(,2$%00%(%2$%0%0

%(

这本身就是一个递归函数，要是按照函数本身写递归式，结果肯定是 789，这里我开

了一个三维数组，从 2$00(开始递推，逐步产生到 2$ 0 0 (的值，复杂度

$:(

总结：这道题是很地道的 ;<，因为它的子问题实在是太多了，所以将问题的结果保

存起来，刘汝佳《算法艺术和信息学竞赛》中 " 页讲到自底向上的递推，这个例子就非

常典型。总体来说这个题目还是非常简单的，不过这个思想是地道的动态规划。

带有详细注释的代码可以在 233!获得

Pku acm 2081 Recaman's Sequence 动态规划题目总结(三)

   

一道很简单的动态规划，根据一个递推公式求一个序列，我选择顺序的求解，即自底

向上的递推，一个  数组 3 根据前面的值依此求出序列的每一个结果，另外一个

 数组 =-.记录  是否已经出现在序列中，求 3 的时候用得着，这样就避免

了查找。核心的 *# 代码为：

6$&+"&,,(

)

6$3-%.%'>>=-3-%.%.63(

)

3-.3-%.%&

=-3-%.%.&

3

)

3-.3-%.,&

=-3-%.,.&

带有详细注释的代码可以在 233!获得

Pku acm 1953 World Cup Noise 动态规划题目总结(四)

4"

给定一个小于 !" 的整数 ，求  位进制数中不含相邻  的数的个数。看似简单的

一道题，如果当 !" 时，对的 !" 次方检查，是无法完成的任务。先分析一下这个问

题：

以  结尾的个数以  结尾的个数总和

  

 

 @ @ @

对于  来说，以  结尾、以  结尾个数都是 ，总和是，下面过度到：对于所

有以  结尾的数，后面都可以加上 ，变为  时以  结尾的，而只有结尾为  的数才能

加上 （因为不能有两个连续 ），这样就可以在  的格里分别填上 、，总和算出

来为 ，以此类推，我们可以算出所有 +!" 的值，然后根据输入进行相应输出。核心

代码如下：

000A-".- .0*&

A-.-.&

A-.-.&

6$ &+"&,,(

)

A-.-.A-%.-.&

A-.-.A-%.-.,A-%.-.&

我们可以继续找出规律，其实这个就是斐波那切数列数列：

B-?.B-?%.,B-?% .&可以继续简化代码。

带有详细注释的代码可以在 233!获得

Pku acm 1458 Common Subsequence 动态规划题目总结(五)

4" 

求两个 3 的最大公共字串，动态规划的经典问题。算法导论有详细的讲解。

下面以题目中的例子来说明算法：两个 3 分别为：6 和 6。创建一个二维

数组 3-.-.0维数分别是两个字符串长度加一。我们定义 3-.-*.表示 C



和 D

*

的最长

子串$85E(当  或 * 等于  时，3-.-*.85E 问题存在一下递归式：

3-.-*.*

3-.-*.3-%.-*%.,C



D

3-.-*./FC$3-%.-*.03-.-*%.(C



GD

对于以上例子，算法如下：

H3-.-*.

   6  

   ! " 

       

  



 



 



6  

 

 

 ! 

    

 " 

    !

从最后一个格向上顺着箭头的方向可以找到最长子串的构成，在有箭头组成的线段中，

含有斜向上的箭头对应的字符是其中的一个 3。

# 代码的核心部分如下：

6$&+&,,()

3-.-.&

6$&+ &,,()

3-.-.&

6$&+&,,()

6$*&*+ &*,,()

6$3F$%(3 F$*%((

3-.-*.3-%.-*%.,&

3

3-.-*.    3-%.-*.'3-.-*%.3-%.-*.3-.-*%

.&

EA3$3-.- .(&

带有详细注释的代码可以在 233!获得

Pku acm 2250 Compromise 动态规划题目总结(六)

  " 

这个也是求最长公共字串，只是相比 5E3I 需要记录最长公共字

串的构成，此时箭头的标记就用上了0在程序中，用 -.-.存放标记， 表示朝向左上方，

 表示指向上，% 表示指向左。3-.-.存放当前最大字串长度。在求最优解时，顺着箭

头从后向前寻找公共字串的序号，记录下来，输出即可。该算法在算法导论中有详细的讲

解。

带有详细注释的代码可以在 233!获得。

Pku acm 1159 Palindrome 动态规划题目总结(七)

 "4 

给一个字符串，求这个字符串最少增加几个字符能变成回文，如 F 可以增加

个字符变为回文：FF。通过这样的结论可以和最长公共子串联系起来$未证明(：E

和 EJ$注EJ是 E 的反串(的最长公共子串其实一定是回文的。这样我们就可以借助 3 来解

决该题，即用 3 的长度减去 3 的值即可。核心的 # 代码为：

%85E$302EKL$3(#3$(E$((&

函数 85E 返回两个 3 的 3 的长度

带有详细注释的代码可以在 233!获得

Pku acm 1080 Humman Gene Function 动态规划题目总结(八)

  

这是一道比较经典的 DP，两串基因序列包含 A、C、G、T，每两个字母间的匹配都会

产生一个相似值，求基因序列（字符串）匹配的最大值。

这题有点像求最长公共子序列。只不过把求最大长度改成了求最大的匹配值。用二维

数组 opt[i][j]记录字符串 a 中的前 i 个字符与字符串 b 中的前 j 个字符匹配所产生的最大值。

假如已知 AG 和 GT 的最大匹配值，AGT 和 GT 的最大匹配值，AG 和 GTT 的最大匹配值，

求 AGT 和 GTT 的最大匹配值，这个值是 AG 和 GT 的最大匹配值加上 T 和 T 的匹配值，

AGT 和 GT 的最大匹配值加上 T 和-的匹配值，AG 和 GTT 的最大匹配值加上-和 T 的匹配

值中的最大值，所以状态转移方程：

opt[i][j] = max(opt[i-1][j-1]+table(b[i-1],a[j-1]),opt[i][j-1]+table('-',a[j-1]),opt[i-1][j]

+table('-',b[i-1]));

? F M 7 M F 7 M

剩余18页未读，继续阅读

bill_108

粉丝: 17
资源: 5

会员权益专享

ACM动态规划总结 动态规划经典题傻瓜式讲解

3、动态规划必练题（含解法）.pdf

NOIP2016专题 ——动态规划 by kqp

动态规划经典教程 acm

acm0基础动态规划

河南省acm历年真题

acm经典c语言算法代码

acm国际大学生程序设计竞赛试题与解析

ACM-ICPC真题

codeforces动态规划题单

山东省2018acm试题

acm黑书与白书的难度对比

acm国际大学生程序设计竞赛真题

举例一道ACM题

python ACM树结构

上海交通大学acm 模板

acm国际大学生程序设计竞赛知识与入门 俞勇 pdf

java面试acm模式

中山大学acm模板.pdf

请通过acm分析如何解决主人公的问题

acm程序设计竞赛基础教程(第2版 ) pdf

会员权益专享

最新资源

ACM动态规划总结动态规划经典题傻瓜式讲解

acm国际大学生程序设计竞赛知识与入门俞勇 pdf