首页 > 代码库 > [LeetCode] Triangle

[LeetCode] Triangle

2024-07-12 12:05:48   219人阅读

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.

 

方法一：

数组f，f[i,j] 表示从（0,0）到（i,j）的路径最小和，然后比较最后一行的最小值。top to down方法

 1 class Solution { 2     public: 3     // form top to down 4     int minimumTotal(vector<vector<int> > &triangle) { 5  6         size_t rowNum = triangle.size(); 7         if(rowNum == 0) 8             return 0; 9 10         vector<vector<int> >f(rowNum);11 12         for(size_t i = 0 ; i< rowNum; i++)13         {14             f[i].resize(i+1, 0);15         }   16 17         for(size_t i = 0 ; i< rowNum; i++)18         {   19             //printVector(triangle[i]);20         }   21 22     23         f[0][0] = triangle[0][0];24         for(size_t i = 1 ; i< rowNum; i++)25         {   26             for(size_t j = 0; j <= i; j++)27             {   28                 if(j == 0)29                     f[i][j] = f[i-1][j] + triangle[i][j];30                 else if(j == i)31                     f[i][j] = f[i-1][j-1] + triangle[i][j];32                 else33                 {34                     int a = f[i-1][j-1];35                     int b = f[i-1][j];36                     f[i][j] = min(a, b) + triangle[i][j];37                 }38             }39         }40 41         int res = INT_MAX;42         for(size_t i = 0 ; i< rowNum; i++)43         {44            // printVector(f[i]);45             res = min(res, f[rowNum-1][i]);46         }47 48         return res;49     }50 };


联系
我们