程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記:Triangle

leetcode筆記:Triangle

編輯:關於C++

一. 題目描述

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

二. 題目分析

使用動態規劃來完成。設從頂部到第i層的第k個頂點的最小路徑長度表示為f(i, k),則f(i, k) = min{f(i-1,k), f(i-1,k-1)} + d(i, k),其中d(i, k)表示原來三角形數組裡的第i行第k列的元素。則可以求得從第一行到最終到第length-1行第k個元素的最小路徑長度,最後再比較第length-1行中所有元素的路徑長度大小,求得最小值。

這裡需要注意邊界條件,即每一行中的第一和最後一個元素在上一行中只有一個鄰居。而其他中間的元素在上一行中都有兩個相鄰元素。

三. 示例代碼

class Solution {
public:
    int minimumTotal(vector > &triangle) {
            vector< vector >::size_type length = triangle.size();
            if(length == 0){
                return 0;
            }
            int i, j;
            for(i=1;i::size_type length_inner = triangle[i].size();
                for(j=0;j

 

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