資訊專欄INFORMATION COLUMN
摘要：第一種方法是很早之前寫的，先對(duì)三角形兩條斜邊賦值，和分別等于兩條斜邊上一個(gè)點(diǎn)的和與當(dāng)前點(diǎn)的和。然后套用動(dòng)規(guī)公式進(jìn)行橫縱坐標(biāo)的循環(huán)計(jì)算所有點(diǎn)的，再遍歷最后一行的，找到最小值即可。
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.
NoticeBonus 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.
ExampleGiven 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方法是很早之前寫的，先對(duì)三角形兩條斜邊賦值，sum[i][0]和sum[i][i]分別等于兩條斜邊上一個(gè)點(diǎn)的sum[i-1][0]和sum[i-1][i-1]與當(dāng)前點(diǎn)的和。
然后套用動(dòng)規(guī)公式進(jìn)行橫縱坐標(biāo)的循環(huán)計(jì)算所有點(diǎn)的path sum，再遍歷最后一行的path sum，找到最小值即可。
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];
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/65787.html
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...
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...
摘要：建立兩個(gè)堆，一個(gè)堆就是本身，也就是一個(gè)最小堆另一個(gè)要寫一個(gè)，使之成為一個(gè)最大堆。我們把遍歷過(guò)的數(shù)組元素對(duì)半分到兩個(gè)堆里，更大的數(shù)放在最小堆，較小的數(shù)放在最大堆。同時(shí)，確保最大堆的比最小堆大，才能從最大堆的頂端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...
摘要：首先，我們應(yīng)該了解字典樹的性質(zhì)和結(jié)構(gòu)，就會(huì)很容易實(shí)現(xiàn)要求的三個(gè)相似的功能插入，查找，前綴查找。既然叫做字典樹，它一定具有順序存放個(gè)字母的性質(zhì)。所以，在字典樹的里面，添加，和三個(gè)參數(shù)。 Problem Implement a trie with insert, search, and startsWith methods. Notice You may assume that all i...
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...
閱讀 1250·2021-11-15 11:37
閱讀 2260·2021-09-30 09:55
閱讀 4539·2021-09-22 15:51
閱讀 3760·2021-09-22 15:46
閱讀 2781·2019-08-30 15:52
閱讀 438·2019-08-29 16:20
閱讀 2903·2019-08-29 15:12
閱讀 1163·2019-08-26 18:27
