详细见：leetcode.com/problems/triangle
Java Solution: github
package leetcode; /* * Given a triangle, find the minimum path sum from top to bottom. * Each step you may move to adjacent numbers on the row below. For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle. */ import java.util.List; public class P120_Triangle { public static void main(String[] args) { List<List<Integer>> list = tools.Utils.C_生成List_List_Integer__从二维数组(new int[][] { {1}, {-1, 1}, // {0, 2, 3}, // {0, 4, 5, 6}, // {1, 0, 3, 6, 9} }); Solution2 s = new Solution2(); System.out.println(s.minimumTotal(list)); } /* * TLE */ static class Solution { int min = Integer.MAX_VALUE; int I = 0; public int minimumTotal(List<List<Integer>> triangle) { I = triangle.size() - 1; if (I < 0) { return 0; } else if (I == 0) { return triangle.get(0).get(0); } return search(triangle, 0, 0); } private int search(List<List<Integer>> triangle, int i, int j) { if (j < 0 || j > i) { return Integer.MAX_VALUE; } if (i == I) { return triangle.get(i).get(j); } return Math.min(search(triangle, i + 1, j), search(triangle, i + 1, j + 1)) + triangle.get(i).get(j); } } /* * 艰难AC * 3 ms */ static class Solution2 { public int minimumTotal(List<List<Integer>> triangle) { int len = 0; if (triangle == null || (len = triangle.size()) <= 0) { return 0; } else if (len == 1) { return triangle.get(0).get(0); } int[] arr = new int[len + 1]; for (int list_count = len - 1; list_count > -1; list_count --) { List<Integer> list_now = triangle.get(list_count); arr[0] = list_now.get(0) + Math.min(arr[0], arr[1]); for (int i = 1; i <= list_count; i ++) { arr[i] = list_now.get(i) + Math.min(arr[i], arr[i + 1]); } } return arr[0]; } } }C Solution: github
/* url: leetcode.com/problems/triangle AC 6ms 4.76% */ #include <stdio.h> #include <stdlib.h> #include <limits.h> long _min(long* m, int i, int j, int k) { if (i == -1) return m[j]; if (j >= k) return m[i]; return m[i] < m[j] ? m[i] : m[j]; } int minimumTotal(int** t, int rn, int *cn) { int i = 0, j = 0; long ans = LONG_MAX; long* m = NULL; if (rn < 1) return 0; m = (long*) malloc(sizeof(long) * cn[rn-1]); for (j = 0; j < cn[rn-1]; j ++) m[j] = 0l; m[0] = t[0][0]; for (i = 1; i < rn; i ++) { for (j = cn[i]-1; j > -1; j --) m[j] = t[i][j] + _min(m, j-1, j, cn[i-1]); } for (j = 0; j < cn[rn-1]; j ++) ans = ans > m[j] ? m[j] : ans; free(m); return ans; }Python Solution: github
#coding=utf-8 ''' url: leetcode.com/problems/triangle @author: zxwtry @email: zxwtry@qq.com @date: 2017年5月4日 @details: Solution: 68ms 26.43% ''' class Solution(object): def minimumTotal(self, t): """ :type t: List[List[int]] :rtype: int """ tn = 0 if t == None else len(t) if tn == 0: return 0 m = [0]*tn m[0] = t[0][0] for i in range(1, tn): for j in range(i, -1, -1): m[j] = t[i][j] + min(m[j-1] if j == i else m[j], m[j] if j==0 else m[j-1]) return min(m) if __name__ == "__main__": t = [[-1],[2,3],[1,-1,-3]] print(Solution().minimumTotal(t))