首页 > 代码库 > Triangle <leetcode>

Triangle <leetcode>

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.

 

算法:首先想到的是DFS,但是超时了代码如下:

class Solution {public:    int  result;    int minimumTotal(vector<vector<int> > &triangle) {        result=0;        doit(triangle,0,0,0);        return result;    }    void doit(vector<vector<int>>  &triangle,int level,int key,int sum)    {        if(level==triangle.size())        {           if(sum>result)  result=sum;           }        if(level<triangle.size()-1)        {           doit(triangle,level+1,key,sum+triangle[level][key]);           doit(triangle,level+1,key+1,sum+triangle[level][key]);        }    }};

  在网上查到的动态规划算法,从下到上,要求第i层到最底层路径的最小和,只要知道i+1层到最底层的最小路径和,代码如下:

class Solution {public:    int minimumTotal(vector<vector<int> > &triangle) {            int len=triangle.size();        if(len==0)  return -1;        if(triangle[len-1].size()!=len)  return -1;        int *temp=new int[len];        for(int i=0;i<len;i++)        {            temp[i]=triangle[len-1][i];        }        for(int i=len-2;i>=0;i--)        {            for(int j=0;j<=i;j++)            {                temp[j]=triangle[i][j]+min(temp[j],temp[j+1]);            }        }        return temp[0];    }   };

  

Triangle <leetcode>