这个题目我第一次看，以为是直接找每一行最小值就行（不仔细审题的结果）。但是人家要求是要相邻的。然后又在头疼这个位置相邻该怎么表示。最后想到是不是贪心策略（其实当时我并不会贪心法，只是看着像）。然后实在做不出来，就去看了一下答案，然后打开了新世界…下面看一下该怎么解。
首先要知道的是这个问题使用动态规划比较好。然后有两种方式去遍历这个三角形求解，分别是从上往下遍历（top—down）和从下往上遍历（down—top）。先说一下从下往上遍历，这种容易理解些。说思路前，我们先把这个三角形变为直角三角形，那样子看起来更直观一些，而且答案不会改变，因为各个点的邻接关系并没有改变。即是这样：
[[2],[3,4],[6,5,7],[4,1,8,3]
]
那就说一下从下往上遍历的思路。动态规划的思路就是记住每一次的最优状态。比如这个问题我们可以申请一个二维数组dp[4][4]，我们对最后一层每个点，记住一个最优状态（最小值），这个时候其实存储的就是各个点各自的值，此时dp的值为{
{}, {}, {}, {4,1,8,3}}；然后看倒数第二层，对于每个点，我们求它的最优状态应该为它自己的值分别加上下一层相邻两个值中的最小值，即针对于第i层第j个节点，dp[i][j] = Math.min[(dp[i+1][j] ,dp[i+1][j+1]) + dp[i,j];，比如对于倒数第二层的6，它的最优状态应该为Math.min(4, 1) + 6 = 7，最后得到的dp，其中dp[0][0]也就是最后的值，代码如下：
public static int minimumTotal1(List<List<Integer>> triangle) {
int[][] dp = new int[triangle.size()][triangle.size()];int layer = triangle.size() - 1;for (int i = 0; i <= layer; ++i)dp[layer][i] = triangle.get(layer).get(i); //最后一层就是它本身layer--; //直接从倒数第二层开始计算就行while (layer >= 0) {
for (int i = 0; i <= layer; ++i) //dp存这个点的值加上它下一层相邻两个点中最小值dp[layer][i] = Math.min(dp[layer + 1][i], dp[layer+1][i + 1]) + triangle.get(layer).get(i);layer--;}return dp[0][0];}
那你以为这样就完了吗，看题目下面的提示，是的我们使用的空间复杂度是O(n2)，人家要求最好是O(n)。
那我们有哪个地方需要改进呢。其实也很简单，肯定是这个dp数组，那我们分析一下会发现每次更新dp的时候都只依赖它的下一层，和再下一层都没有关系。那这样就好办多了，我们把dp数组改成一个n维，然后只存上一层的dp，同时又可以将当前层更新后的dp放进去，做到边使用变更新就好了。画个图好理解一些（图比较糙），这样就可以了，代码也是比较简单，只是不如上面那个好理解：
public int minimumTotal(List<List<Integer>> triangle) {
int[] dp = new int[triangle.size() + 1];for (int i = triangle.size()-1; i >= 0; --i) {
for (int j = 0; j < triangle.get(i).size(); j++) {
dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);}}return dp[0];}