程序员必知:动态规划备忘录方法

简介: 程序员必知:动态规划备忘录方法

一、动态规划要点

1 最优子结构性质

当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。

2 重叠子问题性质

动态规划算法对每个问题只解一次,将其解保存在一个表格中,当再次需要解此问题时,用常数时间查看一下结果。因此,用动态规划算法通常只需要多项式时间。

二、备忘录方法要点

备忘录方法:

1 用一个表格来保存已解决的子问题的答案,用的时候查表即可。

2 采用的递归方式是自顶向下。

3 控制结构与直接递归相同,区别在于备忘录方式为每个解过//代码效果参考:http://www.zidongmutanji.com/bxxx/516486.html

的子问题建立备忘录。

4 初始化为每个子问题的记录存入一个特殊的值,表示并未求解。在求解过程中,查看相应记录如果是特殊值,表示未求解,否则只要取出该子问题的解答即可。

三、动态规划和备忘录方法的区别

1、动态规划是自低向上 ,备忘录方法是自顶向下。

2、动态规划每个子问题都要解一次,但不会求解重复子问题;备忘录方法只解哪些确实需要解的子问题。

四、矩阵连乘问题

动态规划四个步骤

1. 找出最优解的性质,并且刻画其结构特性;

2. 递归的定义最优解;

3. 以自底向上的方式刻画最优值;

4. 根据计算最优值时候得到的信息,构造最优解

一般来讲,当一个问题的所有子问题都至少要解一次时,使用动态规划算法比使用备忘录方法好。此时,动态规划算法没有任何多余的计算。同时,对于许多问题,常常可以利用其规则的表格存取方式,减少动态规划算法的计算时间和空间需求。当子问题空间中的部分子问题可以不必求解时,使用备忘录方法则较为有利,因为从其控制结构可以看出,该方法只解那些确实需要求解的问题。

对于动态规划算法,我们必须明确两个基本要素,这两个要素对于在设计求解具体问题的算法时,是否选择动态规划算法具有指导意义:

1 算法有效性依赖于问题本身所具有的最优子结构性质:设计算法的第一步通常是要刻画最优解的结构。当问题的最优解包含了子问题的最优解时,称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可以使用动态规划算法求解的重要线索

在矩阵连乘积最优次序问题中注意到,若A1A2...An的最优完全加括号方式在Ak和Ak+1之间断开,则由此可以确定的子链A1A2A3...Ak和Ak+1Ak+2...An的完全加括号方式也最优,即该问题具有最优子结构性质。在分析该问题的最优子结构性质时候,所使用的方法具有普遍性。首先假设由原问题导出的子问题的借不是最优解,然后在设法说明在这个假设下可以构造出//代码效果参考:http://www.zidongmutanji.com/bxxx/23840.html

比原问题最优解更好的解,从而导致矛盾。

在动态规划算法中,利用问题的最优子结构性质,以自底向上的方式递归的从子问题的最优解逐渐构造出整个问题的最优解。算法考察的子问题的空间规模较小。例如在举证连乘积的最优计算次序问题中,子问题空间由矩阵链的所有不用的子链组成。所有不用的子链的个数为o(nn),因而子问题的空间规模为o(nn)

2 可以用动态规划算法求解问题应该具备另一个基本要素是子问题的重叠性。在用递归算法自顶向下求解此问题时候,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题都只是求解一次,而后将其保存到一个表格中,当再次需要解此问题时,只是简单使用常数时间查看一下结果。通常,不同子问题个数随着问题大小呈多项式增长。因此使用动态规划算法通常只是需要多项式时间,从而获得较高的解题效率。

下面是使用动态规划算法求解矩阵连乘问题的Java实现:

1 package dynamic_planning;

2

3 public class Strassen {

4 /

5 array【i】【j】表示Ai...Aj相乘最少计算次数

6 s【i】【j】=k,表示Ai...Aj这(j-i+1)个矩阵中最优子结构为Ai...Ak和A(k+1)...Aj

7 p【i】表示Ai的行数,p【i+1】表示Ai的列数

8 /

9 private int array【】【】;

10 private int p【】;

11 private int s【】【】;

12

13 public Strassen(){

14 p=new int【】{2,4,5,5,3};

15 array=new int【4】【4】;

16 s=new int【4】【4】;

17 }

18

19 public Strassen(int n,int 【】p){

20 this.p=new int【n+1】;

21 this.array=new int【n】【n】;

22 this.s=new int【4】【4】;

23 for(int i=0;i

24 this.p【i】=p【i】;

25 }

26 /**方法一,动态规划**/

27 public void martixChain(){

28 int n=array.length;

29 for(int i=0;i

30 array【i】【i】=0;

31 for(int r=2;r<=n;r++){

32 for(int i=0;i<=n-r;i++){

33 int j=i+r-1;

34 array【i】【j】=array【i+1】【j】+p【i】p【i+1】p【j+1】;

35 s【i】【j】=i;

36 for(int k=i+1;k

37 int t=array【i】【k】+array【k+1】【j】+p【i】p【k+1】p【j】;

38 if(t[span style="color: rgba(0, 0, 0, 1)">array【i】【j】){

39 array【i】【j】=t;

40 s【i】【j】=k;

41 }

42 }

43 }

44 }

45 }

46 /

47 如果待求矩阵为:Ap...Aq,then a=0,b=q-p

48 /

49 public void traceBack(int a,int b){

50 if(a[span style="color: rgba(0, 0, 0, 1)">b){

51 traceBack(a, s【a】【b】);

52 traceBack(s【a】【b】+1, b);

53 System.out.println("先把A"+a+"到A"+s【a】【b】+"括起来,在把A"+(s【a】【b】+1)+"到A"+b+"括起来,然后把A"+a+"到A"+b+"括起来");

54 }

55 }

56

57 /**方法二:备忘录方法*/

58 public int memorizedMatrixChain(){

59 int n=array.length;

60 for(int i=0;i

61 for(int j=i;j

62 array【i】【j】=0;

63 }

64 return lookUpChain(0,n-1);

65 }

66

67 public int lookUpChain(int a,int b){

68 if(array【a】【b】!=0)

69 return array【a】【b】;

70 if(a==b)

71 return 0;

72 array【a】【b】=lookUpChain(a, a)+lookUpChain(a+1, b)+p【a】p【a+1】p【b+1】;

73 s【a】【b】=a;

74 for(int k=a+1;k

75 int t=lookUpChain(a, k)+lookUpChain(k+1, b)+p【a】p【k+1】p【b+1】;

76 if(t[span style="color: rgba(0, 0, 0, 1)">array【a】【b】){

77 array【a】【b】=t;

78 s【a】【b】=k;

79 }

80 }

81 return array【a】【b】;

82 }

83 public static void main(String【】 args) {

84 Strassen strassen=new Strassen();

85 //strassen.martixChain();

86 strassen.memorizedMatrixChain();

87 strassen.traceBack(0, 3);

88 }

89 }

五、最长公共子序列问题LCS

1、公共子序列

子序列:给定一个序列X=,另一个序列Z=,存在一个严格递增的X的下标序列,满足对所有的j=1,2,…,k,xij = zj

公共子序列:给定两个序列X和Y,Z同时是X和Y的子序列,称Z是X和Y的公共子序列。

2、LCS的最优子结构

令X=和Y=为两个序列,Z=为X和Y的任意LCS

(1) 如果xm=yn,那么zk=xm=yn且Zk-1是Xm-1Yn-1的一个LCS

(2) 如果xm≠yn,那么zk≠xm意味着Z是Xm-1和Y的一个LCS

(3) 如果xm≠yn,那么zk≠yn意味着Z是X和Yn-1的一个LCS

3、递归解

c【i,j】是Xi和Yj的LCS长度

c【i,j】

= 0 , i=0且j=0

= c【i-1,j-1】 ,i,j>0且xi=yi

= max(c【i,j-1】,c【i-1,j】), i,j>0且xi≠yj

4、例子

X:ABCBDAB Y:BDCABA => LCS:BCBA

动态规划算法:声明了一个m+1*n+1大小的table,0行0列初始化为0,然后从左往右,从上往下地按照递归解填表。填表结束后通过Print可以递归地按同样的方法打印出所求的子序列。

1 LCS-LENGTH(X,Y)

2 m=X.length+1

3 n=Y.length+1

4 let c【0..m,0..n】 be new table

5 for i=0 to m

6 c【i,0】 = 0

7 for j=0 to n

8 c【0,j】 = 0

9 for i=0 to m

10 for j=1 to n

11 if x【i】==y【j】

12 c【i,j】=c【i-1,j-1】+1

13 else if c【i-1,j】>=c【i,j-1】

14 c【i,j】=c【i-1,j】

15 else c【i,j】=c【i,j-1】

16 return c

17

18 PRINT-LCS(c,X,i,j)

19 if i==0 and j==0

20 return

21 if c【i,j】==c【i-1,j-1】+1

22 PRINT-LCS(c,X,i-1,j-1)

23 print x【i】

24 else if c【i,j】=c【i-1,j】

25 PRINT-LCS(c,X,i-1,j)

26 else

27 PRINT-LCS(c,X,i,j-1)

备忘录方法:用于将table初始化,0行0列都为0,其他元素都为-1,表示备忘录没有记录这些元素,初始化完成调用LCS_RECUR函数。

LCS_RECUR函数:如果备忘录已经有记录直接返回,否则递归地查表并回填备忘录的当前位置。

1 LCS_MEMORIZED(c, X, Y)

2 m=X.length+1

3 n=Y.length+1

4 let c【0..m,0..n】 be new table

5 for i=0 to m

6 c【i,0】 = 0

7 for j=0 to n

8 c【0,j】 = 0

9 for i=0 to m

10 for j=0 to n

11 c【i,j】 = -1

12 return LCS_RECUR(c,X,Y,m,n)

13

14 LCS_RECUR(c,X,Y,i,j)

15 if c【I,j】 ≠ -1

16 return c【I,j】

17 if x【i-1】==y【j-1】

18 lcs = LCS_RECUR(c,x,y,i-1,j-1)+1

19 else

20 up = LCS_RECUR(c,x,y,i-1,j)

21 left = LCS_RECUR(c,x,y,i,j-1)

22 lcs = max(up, left)

23 c【i,j】 = lcs

24 return lcs

对比:

方法比较

1、动态规划法是自底向上,仅通过迭代就可以完成,观察C表的填充顺序,是从上至下从左至右依次填充。当填充完毕后可以得到任意位置(任意子序列)的LCS。

备忘录法是自顶到底,递归地填充C表,仅会填充计算当前LCS会用到的项,所以当执行完毕后还有许多元素尚未填充,意味着只能得到部分子序列的LCS。

2、时间复杂度

两种方法的时间复杂度都是O(mn),因为都需要维护C【m】【n】的表。如果更细致地比较备忘录法需要填充的元素较少,填充过程的代价是O(max(m,n)),而动态规划法填充过程的代价是O(mn),但是实际上备忘录法初始化复杂度是O(mn),并且递归调用也会在常数项上增加时间代价。所以两种方法实际的执行速度差别不大。

3、空间复杂度:O(mn)

相关文章
|
5月前
|
机器学习/深度学习 人工智能 算法
程序员必知:动态规划备忘录方法
程序员必知:动态规划备忘录方法
42 0
|
5月前
|
算法 Java 程序员
Java多态:不只是代码,更是思想的碰撞!
【6月更文挑战第17天】Java的多态性展示了编程的哲学,通过抽象基类(如`AudioFile`、`Shape`、`Product`)和重写方法实现。案例中,音乐播放器利用多态统一处理不同音频格式,绘图软件优雅地绘制各种形状,电商系统灵活管理商品信息。多态简化代码,增强可扩展性,连接技术与设计,体现代码的灵活性和艺术性。
40 0
|
6月前
|
设计模式 Java 开发者
一目了然!谁能想到Java多线程设计模式竟然被图解,看完不服不行
多线程设计模式在Java编程中起着至关重要的作用,它能够有效提高程序的执行效率,使得程序在处理大量数据和复杂任务时更加高效。然而,对于初学者来说,理解和应用多线程设计模式可能是一项相当具有挑战性的任务。为了让读者更加轻松地掌握这一复杂主题,我们带着一种全新的图解方式,深入剖析Java多线程设计模式的精髓。
|
11月前
|
C语言
近期一系列个人做题反复记不住以及思路不清晰问题的总结
近期一系列个人做题反复记不住以及思路不清晰问题的总结
47 0
|
算法
【算法挨揍日记】day01——双指针算法_移动零、 复写零
题目: 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 请注意 ,必须在不复制数组的情况下原地对数组进行操作。
43 0
|
数据安全/隐私保护
机房收费系统—经典代码
机房收费系统—经典代码
|
设计模式 人工智能 程序员
感觉自己的代码很乱?因为你不懂套路
编程教室开了这么久,已经有很多人从完全零基础的小白成为了会写代码的菜鸟程序员,能够自己独立开发程序。不过到此阶段,常常会遇到瓶颈,感觉功能可以实现
|
存储 算法
数据结构上机实践第九周项目3 - 利用二叉树遍历思想解决问题
数据结构上机实践第九周项目3 - 利用二叉树遍历思想解决问题
140 0
数据结构上机实践第九周项目3 - 利用二叉树遍历思想解决问题
|
算法 C++
C++ 基础复习系列2(打印图形类(循环)经典问题类)
C++ 基础复习系列2(打印图形类(循环)经典问题类)
C++ 基础复习系列2(打印图形类(循环)经典问题类)
|
人工智能
每天两道 CodeForces 构造/思维题 (day5)
每天两道 CodeForces 构造/思维题 (day5)
每天两道 CodeForces 构造/思维题 (day5)
下一篇
无影云桌面