一、实践题目
数字三角形
二、问题描述
给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。
三、算法描述
定义一个二维数组来记录最短路径a[i][j]。从倒数第二行开始，比较m[i+1][j]和m[i+1][j+1]的大小，取较小值再与自身m[i][j]相加，得出第i行第j列的数到下一行的最短路径，以此往上推，得出第1行到最后一行的最短路径。
四、算法时间及空间复杂度分析（要有分析过程）
每个子问题的比较时间复杂度为O(1),则整个算法的时间复杂度为O(n2)。
定义了一个二维数组来记录最短路径，则空间复杂度为O(n2)
五、心得体会（对本次实践收获及疑惑进行总结）
原本对动态规划的概念不大清楚，但经过编程题的练习后，渐渐对动态规划的算法有了跟清楚的了解。不过对于第二道编程题，很惊奇为什么书本上会想到这么巧妙的算法解法。