算法第三章上机实践报告

①实践题目：

　　数字三角形

②问题描述：

　　给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。

③算法描述：

　　本题明显利用到的是动态规划的算法思想，每个位置的最大路径都由到它左下方与右下方两个位置的最大路径所相关，满足最优子结构。另外，部分位置的最大路径会被两个位置的最大路径利用到，又满足重叠子问题的特征。

④算法时间及空间复杂度分析（要有分析过程）

　　空间复杂度为O（n的平方），因为需要用到n的平方辅助二维数组记录每个位置的最大路径。

　　时间复杂度为O（n的平方），最大路径的比较要比较N的平方次。

⑤心得体会（对本次实践收获及疑惑进行总结）

　　本次实践帮助我更好的理解了动态规划与分治法的不同与相近之处，另外动态规划这一思想的应用帮助我更好地将一个抽象化的问题变得系统化，具体化。这也扩宽了我认识问题的角度，不只是逐条逐列的将问题细化解决，更可以自底向上或者自顶向下地利用问题之间的联系解决问题，给了我方向性的一个指引。我的疑惑更多是在如何巧妙利用这一思想，从本题的下一题最大子段和书中的做法中，我观察到书中的做法更为简单巧妙，利用了一个辅助变量而非整个辅助数组就解决了问题，可以看出对于动态规划方向性的利用，我掌握的还不是很熟练。