+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-03(1)

2019-05(1)

2019-06(1)

2019-07(7)

2019-08(118)

潇洒郎:算法设计实例一:三角形最大/小路径和——Python代码

发布于2020-09-20 17:07     阅读(164)     评论(0)     点赞(7)     收藏(2)


0

1

2

3

4

5

6

7

8

三角形最大/小路径和

本题是一道非常经典且历史悠久的动态规划题,动态规划的入门必做题,在本题中,给定的三角形的行数为 n,并且第 i 行(从 0 开始编号)包含了 i+1 =n个数。如果将每一行的左端对齐,那么会形成一个等腰直角三角形:

观察得到:行编号等于行元素数量,即第5行有5个数字。

方法一:

我们自底而上,而不是自上而下,因为状态转移方程是:

f[i][j] = max(f[i+1][j], f[i+1][j+1]) + triangle[i][j]

而不是:

f[i][j] = max(f[i-1][j-1], f[i-1][j]) + triangle[i][j]

我们不用考虑i=0时等的各种状况。

编程如下:

  1. def triangle_max_sum():
  2. '''自底向上的动态规划算法'''
  3. #定义三角形
  4. triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
  5. n = len(triangle) #三角形行数
  6. # 初始化状态存储空间f,空间复杂度为:n!=n*(n-1)*..*1
  7. f = [[0] * num for num in range(1,n+1)]
  8. #初始化状态空间的最大数组/列表, 因为我们首先使用的是f[i+1]中的数据,
  9. f[n-1] = triangle[n-1]
  10. # 时间复杂度:i*(i+1) = (n-1)*n = n^2 - n = O(n^2)
  11. for i in range(n-2,-1,-1): # 2,1,0
  12. for j in range(i+1):
  13. f[i][j] = max(f[i+1][j], f[i+1][j+1]) + triangle[i][j]
  14. # 例如:f[2][0]= max(f[3][0], f[3][1]) + triangle[2][0]
  15. # = max(4,5) + 2 = 6
  16. # f[2][0]表示自底而上到达数字triangle[2][0]=2 此路径的最大总和
  17. print(f[0][0])
  18. triangle_max_sum()

程序运行结果:

上述求得是最大的数字和,将程序中的max()改为 min(), 即计算最小路径和:

如例,求最小路径和:

  1. def triangle_min_sum():
  2. '''自底而上的动态规划算法'''
  3. #定义三角形
  4. triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
  5. n = len(triangle) #三角形行数
  6. # 初始化状态存储空间f,空间复杂度为:n!=n*(n-1)*..*1
  7. f = [[0] * num for num in range(1,n+1)]
  8. #初始化状态空间的最大数组/列表, 因为我们首先使用的是f[i+1]中的数据,
  9. f[n-1] = triangle[n-1]
  10. # 时间复杂度:i*(i+1) = (n-1)*n = n^2 - n = O(n^2)
  11. for i in range(n-2,-1,-1): # 2,1,0
  12. for j in range(i+1):
  13. f[i][j] = min(f[i+1][j], f[i+1][j+1]) + triangle[i][j]
  14. # 例如:f[2][0]= max(f[3][0], f[3][1]) + triangle[2][0]
  15. # = max(4,5) + 2 = 6
  16. # f[2][0]表示自底而上到达数字triangle[2][0]=2 此路径的最大总和
  17. print(f[0][0])
  18. triangle_min_sum()

算法时间复杂度:O(N^2)
空间复杂度:O(N!),N 为三角形的行数。

方法二:

可以发现,f[i][j]只与 f[i+1][..]有关,而与 f[i+2][..]及之前的状态无关
,因此我们不必存储这些无关的状态。具体地,我们使用两个长度为 n 的一维数组进行转移,
将i+1根据奇偶性映射到其中一个一维数组,那么 i就映射到了另一个一维数组。
这样我们使用这两个一维数组,交替地进行状态转移。
  1. def triangle_max_sum01():
  2. '''自底而上的动态规划算法'''
  3. # 定义三角形
  4. triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
  5. n = len(triangle) # 三角形行数
  6. # 初始化状态存储空间f,空间复杂度为:2n=O(n)
  7. # 初始化状态空间的最大数组/列表
  8. # 两个数组交替存储并应用状态/计算值
  9. f = []
  10. f.append(triangle[n - 1])
  11. f.append(triangle[n - 1])
  12. # 时间复杂度:i*(i+1) = (n-1)*n = n^2 - n = O(n^2)
  13. for i in range(n - 2, -1, -1): # 2,1,0
  14. sm1, sm2 = i % 2, 1 - i % 2 # i根据奇偶性 0,1
  15. for j in range(i + 1):
  16. f[sm1][j] = max(f[sm2][j], f[sm2][j + 1]) + triangle[i][j]
  17. print(f[0][0]) #最终结果都是在第一行第一列
  18. triangle_max_sum01()

运行结果:

算法时间复杂度:O(N^2)
空间复杂度:O(2N)=O(N),N 为三角形的行数

 

方法三:

  1. def triangle_max_sum02():
  2. '''自底而上的动态规划算法'''
  3. # 定义三角形
  4. triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
  5. n = len(triangle) # 三角形行数
  6. # 初始化状态存储空间f,空间复杂度为:n=O(n)
  7. # 初始化状态空间的最大数组/列表
  8. # 只用一个数组存储并应用状态/计算值,对数组本身操作
  9. f = triangle[n - 1] # [4, 5, 2, 6, 5]
  10. # 时间复杂度:i*(i+1) = (n-1)*n = n^2 - n = O(n^2)
  11. for i in range(n - 2, -1, -1): # 2,1,0
  12. for j in range(i + 1):
  13. f[j] = max(f[j], f[j + 1]) + triangle[i][j]
  14. print(f[0])
  15. triangle_max_sum02()

运行结果:

算法时间复杂度:O(N^2)
空间复杂度:O(N),N 为三角形的行数

 

 

 

 

 

 

原文链接:https://blog.csdn.net/qq_32711799/article/details/108630482

0

1

2

3

4



所属网站分类: 技术文章 > 博客

作者:不上班你养我呀

链接: https://www.pythonheidong.com/blog/article/535010/983d3441ad03006955a5/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

7 0
收藏该文
已收藏

评论内容:(最多支持255个字符)