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数组就可以保存结果了：

 1 class Solution {
 2 public:
 3     int minimumTotal(vector<vector<int>>& triangle) {
 4         if(triangle.size() == 0 || triangle[0].size() == 0)
 5             return 0;
 6         //vector<vector<int>>minRet(triangle.size(), vector<int>(triangle[0].size(), 0));
 7         for(int i = 1; i < triangle.size(); ++i){   // i从1开始
 8             for(int j = 0; j < triangle[i].size(); ++j){
 9                 if(j == 0){
10                     triangle[i][j] += triangle[i - 1][0];
11                 }else if(j == triangle[i].size() - 1){
12                     triangle[i][j] += triangle[i - 1][j - 1];
13                 }else{
14                     triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]);
15                 }
16             }
17         }
18         int horSz = triangle.size();
19         int sz = triangle[horSz - 1].size();
20         int ret = triangle[horSz - 1][0];
21         for(int i = 1; i < sz; ++i){
22             if(ret > triangle[horSz - 1][i])
23                 ret = triangle[horSz - 1][i];
24         }
25         return ret;
26     }
27 };

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