算法题 动态规划-数字三角形（Python）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法题 动态规划-数字三角形（Python），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含793字，纯文字阅读大概需要2分钟。

内容图文

题目

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

输入格式

第一行包含整数n，表示数字三角形的层数。

接下来n行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

数据范围

1≤n≤500
?10000≤三角形中的整数≤10000

输入样例：

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

输出样例：

30

代码

n = int(input())
nums = []
for _ in range(n):
    nums.append(list(map(int, input().split())))
    
dp = [0] * (n)
dp[0] = nums[0][0]
for i in range(1, n):
    for j in range(len(nums[i])-1, -1, -1):
        if j == len(nums[i]) - 1: dp[j] = dp[j-1]
        elif j != 0: dp[j] = max(dp[j], dp[j-1])
        dp[j] += nums[i][j]
print(max(dp))
    

 

内容总结

以上是互联网集市为您收集整理的算法题 动态规划-数字三角形（Python）全部内容，希望文章能够帮你解决算法题 动态规划-数字三角形（Python）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---