一、实践题目
数字三角形
二、问题描述
给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。
三、算法描述
使用二维数组m记录每个子问题的最大值，m数组所有元素初始化为-1，如最大值已被计算则更新数值，到达最底层时最大值等于原数组元素本身。
四、算法时间及空间复杂度分析
时间复杂度：数字的总数是n(n+1)/2，对于每一个数字到底边的最大和只需要算一次，时间复杂度是O(n²)。
空间复杂度：使用二维数组储存最大值，空间复杂度是O(n²)。
五、心得体会
填表法的递归方式是自底向上递归求解，而备忘录方法的递归方式是自顶向下递归求解。
当一个问题的所有子问题都至少要解一次时，使用填表法。
当子问题空间中的部分子问题不需要求解时，使用备忘录方法。
原文：https://www.cnblogs.com/XuanChan/p/11703772.html