给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下),使该路径经过的数字总和最大。
创建两个数组,一个数组用于存放数字三角形,一个用于存放从底端开始到达某个元素的最大路径(只创建一个数组也是可以的,然后将结果不断覆盖)。
使用动态规划和便签本的方式来解决这个问题。
递归方程式
m[i][j] = m[i][j] i = n-1
0 <= j <= i
max(m[i+1][j], m[i+1][j+1]) + t[i][j] i < n-1
该算法时间空间复杂度都是O(n2)
动态规划并不是我擅长的部分,尤其是第三题,所以还有很多需要继续学习和进步的地方。
原文:https://www.cnblogs.com/jumaodangdawang/p/11717143.html