L1-数字三角形

Posted on |

题目

给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。
注意事项
如果你只用额外空间复杂度O(n)的条件下完成可以获得加分，其中n是数字三角形的总行数。

样例
比如，给出下列数字三角形：
[

 [2],

[3,4],

[6,5,7],

[4,1,8,3]

]

从顶到底部的最小路径和为11 ( 2 + 3 + 5 + 1 = 11)。

复杂度o(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    /**
     * @param triangle: a list of lists of integers
     * @return: An integer, minimum path sum
     */
   
      public int minimumTotal(int[][] triangle) {
        // write your code here
        if(triangle.length==1&&triangle[0].length==1)
            return triangle[0][0];
        int minnum = Integer.MAX_VALUE;
      
        for(int i=1;i<triangle.length;i++){
            for(int j=0;j<triangle[i].length;j++){
                if(j==0){
                    triangle[i][j]+=triangle[i-1][j];
                }else if(j==triangle[i].length-1){
                    triangle[i][j]+=triangle[i-1][j-1];
                }else{
                    triangle[i][j]+=Math.min(triangle[i-1][j],triangle[i-1][j-1]);
                }
              //把每一行的元素改为其下一行能与之相加的两个数得到的和的最小值
                if(i==triangle.length-1)
                    minnum = Math.min(minnum,triangle[i][j]);
            }
        }
        return minnum;
    }
}

思路

常规的动态规划解法，求出从顶点到底部所有节点的路径，在选取最小的路径和.这里给的是下三角矩阵

走到i，j就只有两种情况，一种是从i-1,j-1过来，一种是从i-1,j过来。
找到状态转移方程：

dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j];

然后初始化dp，利用状态转移方程算出结果

动态规划例题

image

image
image