【题目描述】
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。
【注】：如果你只用额外空间复杂度O(n)的条件下完成可以获得加分，其中n是数字三角形的总行数。
【题目链接】
www.lintcode.com/en/problem/triangle/
【题目解析】
首先来看自顶向下，根据题目我们知道，每向下一层，我们只能选择邻接数字进行累加，譬如上面第1行的数字3，它的下一行邻接数字就是6和5。
我们假设dp[m][n]保存了第m行第n个节点的最小路径和，我们有如下dp方程
·dp[m + 1][n] = min(dp[m][n], dp[m][n - 1]) + triangle[m + 1][n] if n > 0
·dp[m + 1][0] = dp[m][0] + triangle[m + 1][0]
因为想要使用O(n)的空间，所以需要滚动计算，使用一个一位数组保存每层的最小路径和。为了防止计算的时候不覆盖以前的值，所以我们需要从后往前计算。
【参考答案】
