程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode| Triangle 三角矩陣的最小路徑和

LeetCode| Triangle 三角矩陣的最小路徑和

編輯:C++入門知識

LeetCode| 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, wheren is the total number of rows in the triangle.

給定一個三角矩陣 從最上層到最下層的距離最小,下層選擇的數和上層選擇的數必須是相鄰的

思路:

這是一個典型的DP問題,如果設定dp[i][j]表示從最上層到當前元素的路徑的最小值,那麼到矩陣都被設置後,從最後一層中找到最小的即可。

只不過需要注意的是每一層的第一個元素和最後一個元素,因為這兩個位置的相鄰元素只有一個。初始化dp[0][0]為三角矩陣的第一個元素的值。

 

int Path(vector >& triangle)
{
	vector > dp(triangle.size());
	int i,j;
	int tmp;
	int min;
	for(i=0;i > triangle(4);
	int i,j;
	srand(rand()%100000);
	for(i=1;i<=4;i++)
		triangle[i-1].assign(i,0);
	
	for(i=0;i

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved