首页 > 代码库 > LeetCode Triangle

LeetCode Triangle

2024-08-11 15:19:34   215人阅读

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 is11(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.


思路：从下往上，每一行的结果根据下面一行的路基累计和而计算。（参考大神才晓得） 
triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]) 
对于此题子在面试的时候， 除了题意，还要要问清楚这些题的其他问题，比如 ：传递的数据元素可以修改否？ 最后求出的和sum会不会超出integer的范围？ 

package cn.edu.algorithm.huawei;

import java.util.ArrayList;

public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return -1;
        }

        int len = triangle.size();
        int[][] dp = new int[len][len];

        for (int i = 0; i < len; i++) {
            dp[len - 1][i] = triangle.get(len - 1).get(i);
        }

        for (int i = len - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }

    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> triangle = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> list1 = new ArrayList();
        list1.add(1);

        ArrayList<Integer> list2 = new ArrayList();
        list2.add(2);
        list2.add(3);

        triangle.add(list1);
        triangle.add(list2);

        Solution s = new Solution();
        int path = s.minimumTotal(triangle);
        System.out.println(path);
    }
}
 
 
LeetCode Triangle






























        

            
                
                  
                
                

                    联系

                    我们