[leetcode]Triangle

新博文地址：[leetcode]Triangle

Triangle

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.

 求三角形从上到下的最短路径，最好能将空间复杂度达到O(n)，这道题有两种做法：

一种是破坏原数组，这样就不需要额外空间

另一种是保留原数组，需要O(n)空间，无论哪一种都满足题中对空间复杂度的要求。

 

我的算法是，用一个数组记录从根节点到第 i 层的所有节点的路径，从而选出最短路径。需要O(n)空间，代码较长。

	public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
		if (triangle == null || triangle.size() == 0) {
			return 0;
		}
		int size = triangle.size();
		int[] path = new int[triangle.get(size - 1).size()];
		path[0] = triangle.get(0).get(0);
		int[] cpyPath = Arrays.copyOf(path, path.length);//两个一位数组切换
		for (int j = 1; j < triangle.size(); j++) {
			ArrayList<Integer> list = triangle.get(j);
			for (int i = 0; i < list.size(); i++) {
				if (i == 0) {
					cpyPath[0] = path[0] + list.get(0);
				} else if (i == list.size() - 1) {
					cpyPath[i] = list.get(list.size() - 1) + path[list.size() - 2];
				} else {
					int min = path[i - 1] < path[i] ? path[i - 1] : path[i];
					cpyPath[i] = list.get(i) + min;
				}
			}
			path = Arrays.copyOf(cpyPath, cpyPath.length);
		}
		int result = Integer.MAX_VALUE;
		for (Integer tem : path) {
			if (tem < result) {
				result = tem;
			}
		}
		return result;
	}

 可以看出，上面的算法是自顶向下的。

另一种做法是自底向上，破坏了数组内容，但是代码非常简练，而且无需考虑边界条件，真心赞

public int bottomUp(ArrayList<ArrayList<Integer>> triangle) {
		for(int i = triangle.size() - 2; i >= 0; i--){
			for(int j = 0; j < triangle.get(i).size(); j++){
				triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)));
			}
		}
		return triangle.get(0).get(0);		
	}

 但是有人说这是DP问题，可能是我对DP不太熟练，总认为这并不是DP问题，因为它连DP问题最基本的“最优子结构”都不满足。例如

[2],
[3,1],
[6,5,11]

三层结构时，毫无疑问是2,3,5，但是两层时，应该是2,1。而且DP问题的求解顺序也应该是由子问题递推求出原问题。回头再研究研究DP。如果我理解错了，请大家指正