120. Triangle

发布时间:2018-09-11 10:28  浏览次数:20

题目

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.

思路

发现了一个很好的动态规划解题套路。


先从非常naive的角度看这个题:从三角形的顶开始向下走,你此时并不能确定在第二层选择哪一个数字,因为看起来大的那个数字也可能会指向一条数字和小的路径。所以每一个元素及每一个元素下层的邻居元素都要遍历。这不就是典型的backtracking问题么?


我们知道dp是backtracking的一种优化,主要解决了子问题重叠造成的时间浪费,那么当我们对一个问题的dp解法还没有想法的时候,先通过研究backtracking的递归树来看看能不能找到子问题重叠的情况。

以下面这个三角形为例
[0], [1,2], [3,4,5], [6,7,8,9]
它的backtracking递归树:



已经能看出子树重复了,如果再三角形加一层会更加明显,能发现7、8这两个子树也有高度重复。

到这里就非常清晰了,题目中要求O(n) extra space,那么用bottom-up的dp,将每个节点到最底层的最短路径记录下来就可以了。

dp算法:
dp[row][i]: 第row层第i个元素到达底层所需的最短路径 转移方程: dp[row][i] = triangle[i] +
min(dp[row+1][i], dp[row+1][i+1])
此处用的是一个二维数组,按题中要求可压缩成一个一维数组,从底层向高层循环,每次都利用低层的数字算出高层的,然后覆盖数组中的值即可。

实现
1 public int minimumTotal(List<List<Integer>> triangle) { 2 int N =
triangle.size(); 3 int[] min = new int[N]; 4 List<Integer> lastRow =
triangle.get(N - 1); 5 for(int i = 0; i < N; i++) 6 min[i] = lastRow.get(i);
7 8 for(int row = N - 2; row >= 0; row--){ 9 List<Integer> currentRow =
triangle.get(row);10 for(int i = 0; i < row + 1; i++){ 11 min[i] =
currentRow.get(i) + Math.min(min[i], min[i+1]); 12 } 13 } 14 return min[0]; 15
}
复杂度

时间复杂度 = O(三角形中数字数)

空间复杂度 = O(三角形层数)

总结


dp是一种“看别人的答案恍然大悟,但下一次还是不会做”的问题,因为dp的代码形式并不是重点,将会做dp和不会做dp问题的人划分开来的是他们的思路,即“怎么想到要用dp,如何得出状态转换方程”。

作为dp新手,一个思路是试着用backtracking解题并画出递归树,寻找递归树中重叠的子树,这样就抓住了dp问题的关键,状态转换方程会不请自来。

标签

归档

阅读排行

支付宝搜索“559315787”,天天领红包