首页 > 代码库 > Triangle
Triangle
https://oj.leetcode.com/problems/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.
解题思路：
这时一个动态规划的题目，于是寻找状态，和状态间的转换方程。考虑定义一个dp[m][n]，表示到达第m行的n个数，的最小sum值。那么他的状态转换方程很好定义。每行的第一个数的dp，必然等于上一行第一个数的dp+本行第一个数的数值，没有选择。最后一个数同理。其他数字的dp，等于自己的数值，加上上一行头上两个dp中较小的那个。于是又方程如下：
dp[i][j] = dp[i - 1][j] + triangle.get(i).get(j); //j == 0
= dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j); // j == i
=dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle.get(i).get(j); //其他情况
public class Solution { public int minimumTotal(List<List<Integer>> triangle) { if(triangle == null || triangle.size() == 0){ return 0; } //初始化dp数组，原三角形第i行有i + 1个数据，二维长度都为triangle.size() int[][] dp = new int[triangle.size()][triangle.size()]; dp[0][0] = triangle.get(0).get(0); for(int i = 1; i < triangle.size(); i++){ //这里j只要到i就可以了，因为原三角形第i行有i + 1个数据 for(int j = 0; j <= i; j++){ //每行的第一个dp if(j == 0){ dp[i][j] = dp[i - 1][j] + triangle.get(i).get(j); }else if(j == i){//每行的最后一个dp dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j); }else{//其他dp dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle.get(i).get(j); } } } //选出最后一行中最小的数字 int min = Integer.MAX_VALUE; for(int i = 0; i < triangle.get(triangle.size() - 1).size(); i++){ if(dp[triangle.size() - 1][i] < min){ min = dp[triangle.size() - 1][i]; } } return min; }}
原题要求只花线性的额外空间，其实很简单。参考Minimum Path Sum这题，无非是用上行本列的数据和上行本列之前列的数据来更新本行本列的数据。但是细想不对，如果是上行本列之后的可以，之前的，在算dp[m][n]的时候，dp[m][n-1]已经被更新为本行数据了，无法取得上行前列的，只能取得后列。于是，在内循环j的时候，改为从后向前循环，即可。代码如下。
public class Solution { public int minimumTotal(List<List<Integer>> triangle) { if(triangle == null || triangle.size() == 0){ return 0; } //初始化dp数组，原三角形第i行有i + 1个数据，二维长度都为triangle.size() int[] dp = new int[triangle.size()]; dp[0] = triangle.get(0).get(0); for(int i = 1; i < triangle.size(); i++){ //这里j只要到i就可以了，因为原三角形第i行有i + 1个数据 //这个循环从后向前，因为dp必须用后列数据更新前列的 for(int j = i; j >= 0; j--){ // int temp = dp[j]; //每行的第一个dp if(j == 0){ dp[j] = dp[j] + triangle.get(i).get(j); }else if(j == i){//每行的最后一个dp dp[j] = dp[j - 1] + triangle.get(i).get(j); }else{//其他dp dp[j] = Math.min(dp[j], dp[j - 1]) + triangle.get(i).get(j); } } } //选出最后一行中最小的数字 int min = Integer.MAX_VALUE; for(int i = 0; i < triangle.get(triangle.size() - 1).size(); i++){ if(dp[i] < min){ min = dp[i]; } } return min; }}
这道题，从下至上进行dp也可以，具体代码网上有。还有discuss里面的代码很简洁，可读性一般，也比较难理解，可以看看。
Triangle