[LintCode/LeetCode] Triangle

劉德剛發布于2019-08-14 15:28 / 1340人閱讀

摘要：第一種方法是很早之前寫的，先對三角形兩條斜邊賦值，和分別等于兩條斜邊上一個點的和與當前點的和。然后套用動規公式進行橫縱坐標的循環計算所有點的，再遍歷最后一行的，找到最小值即可。

Problem

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

Notice

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.

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

第一種DP方法是很早之前寫的，先對三角形兩條斜邊賦值，sum[i][0]和sum[i][i]分別等于兩條斜邊上一個點的sum[i-1][0]和sum[i-1][i-1]與當前點的和。
然后套用動規公式進行橫縱坐標的循環計算所有點的path sum，再遍歷最后一行的path sum，找到最小值即可。

Solution

DP：

public class Solution {
    public int minimumTotal(int[][] triangle) {
        int n = triangle.length;
        int[][] dp = new int[n][n];
        dp[0][0] = triangle[0][0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i-1][0] + triangle[i][0];
            dp[i][i] = dp[i-1][i-1] + triangle[i][i];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j];
            }
        }
        int res = dp[n-1][0];
        for (int i = 0; i < n; i++) {
            res = Math.min(res, dp[n-1][i]);
        }
        return res;
    }
}

Advanced DP：

public class Solution {
    public int minimumTotal(int[][] A) {
        int n = A.length;
        for (int i = n-2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                A[i][j] += Math.min(A[i+1][j], A[i+1][j+1]);
            }
        }
        return A[0][0];
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65787.html

[LintCode/LeetCode] Word Break

Problem Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words. Example Given s = lintcode, dict = [lint, code]. R...

dunizb 2019-08-14 15:30 評論0 收藏0
[LintCode/LeetCode] First Unique Character in a S

Problem Given a string, find the first non-repeating character in it and return its index. If it doesnt exist, return -1. Example Given s = lintcode, return 0. Given s = lovelintcode, return 2. Tags A...

Xufc 2019-08-15 13:27 評論0 收藏0
[LintCode/LeetCode] Find Median From / Data Stream

摘要：建立兩個堆，一個堆就是本身，也就是一個最小堆另一個要寫一個，使之成為一個最大堆。我們把遍歷過的數組元素對半分到兩個堆里，更大的數放在最小堆，較小的數放在最大堆。同時，確保最大堆的比最小堆大，才能從最大堆的頂端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...

zxhaaa 2019-08-14 14:35 評論0 收藏0
[LintCode/LeetCode] Implement Trie

摘要：首先，我們應該了解字典樹的性質和結構，就會很容易實現要求的三個相似的功能插入，查找，前綴查找。既然叫做字典樹，它一定具有順序存放個字母的性質。所以，在字典樹的里面，添加，和三個參數。 Problem Implement a trie with insert, search, and startsWith methods. Notice You may assume that all i...

付永剛 2019-08-14 15:23 評論0 收藏0
[LintCode/LeetCode] Binary Tree Pruning

Problem Binary Tree PruningWe are given the head node root of a binary tree, where additionally every nodes value is either a 0 or a 1. Return the same tree where every subtree (of the given tree) not...

rockswang 2019-08-16 12:37 評論0 收藏0