LeetCode OJ：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]

]

一开始的题目的意思理解错了，以为是位数相差一就是临近的意思，但实际上这里意思是图形上面的那种临近，和原来那个实际上是不一样的。用到了dfs，我一开始还想用一个min的二位vector来保存结果

但是实际上不用，直接用原来的triangle数组就可以保存结果了：

 class Solution {

 public:

     int minimumTotal(vector<vector<int>>& triangle) {

         if(triangle.size() ==  || triangle[].size() == )

             return ;

         //vector<vector<int>>minRet(triangle.size(), vector<int>(triangle[0].size(), 0));

         for(int i = ; i < triangle.size(); ++i){   // i从1开始

             for(int j = ; j < triangle[i].size(); ++j){

                 if(j == ){

                     triangle[i][j] += triangle[i - ][];

                 }else if(j == triangle[i].size() - ){

                     triangle[i][j] += triangle[i - ][j - ];

                 }else{

                     triangle[i][j] += min(triangle[i - ][j - ], triangle[i - ][j]);

                 }

             }

         }

         int horSz = triangle.size();

         int sz = triangle[horSz - ].size();

         int ret = triangle[horSz - ][];

         for(int i = ; i < sz; ++i){

             if(ret > triangle[horSz - ][i])

                 ret = triangle[horSz - ][i];

         }

         return ret;

     }

 };

这个题用java写还是略坑爹，各种get，add写起来感觉好麻烦，暂时就不写了。

巴特西

LeetCode OJ：Triangle（三角形）

最新文章

热门文章