120. 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]
]

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.

题解

• 题意分析：本题是一道动态规划类型的题目，给出一个三角形，每个位置有一个权值，求其一条经过每层的权值最小的路径的权值是多少。
• 动态规划
  • 思路 1
    • 寻找一条由顶向下的路径，使用path[i][j]表示从顶点(0,0)到结点(i,j)的路径权重
      • 主要考虑当前结点（i，j）可以选择的路径
        • 考虑从(i-1, j)到达该节点的路径 — (j < triangle[i-1].size())
        • 考虑从(i-1, j-1)到达该节点的路径 — (j - 1 >= 0)
  • 思路 2
    • 当然本题也可以考虑从底向顶寻找一条路径，同样使用使用path[i][j]表示从底部到结点(i,j)的路径权重
      • 初始最底部结点 path[i][j] = triangle[i][j]
      • 对于其余非底部结点，主要考虑当前结点（i，j）可以选择的路径
        • 考虑从(i+1, j)到达该节点的路径
        • 考虑从(i+1, j+1)到达该节点的路径
        • path[i][j] = min(path[i+1][j+1], path[i+1][j]) + triangle[i][j];
  • 时间复杂度 — $O(n^2)$
  • 空间复杂度 — $O(n^2)$

实现代码

• 思路 1

  class Solution {
  public:
      int minimumTotal(vector<vector<int>>& triangle) {
  
          int path[triangle.size()][triangle[triangle.size()-1].size()];
  
          path[0][0] = triangle[0][0];
  
          for(int i = 1; i < triangle.size(); ++i) {
              for(int j = 0; j < triangle[i].size(); ++j) {
                  path[i][j] = INT_MAX;
                  if(j - 1 >= 0) path[i][j] = path[i-1][j-1];	
                  if(j < triangle[i-1].size())
                      path[i][j] = min(path[i-1][j], path[i][j]); 
                  path[i][j] += triangle[i][j];
                  // cout << path[i][j] << " ";
              }
              // cout << endl;
          }
  
          int min = INT_MAX;
          for(int i = 0; i < triangle[triangle.size()-1].size(); ++i)
              if(path[triangle.size()-1][i] < min)
                  min = path[triangle.size()-1][i];
  
          return min;
      }
  };

• 思路 2

  class Solution {
  public:
      int minimumTotal(vector<vector<int>>& triangle) {
  
          int path[triangle.size()][triangle[triangle.size()-1].size()];
  
          path[0][0] = triangle[0][0];
  
          for(int j = triangle[triangle.size() - 1].size() - 1; j >= 0; --j) {
              path[triangle.size() - 1][j] = triangle[triangle.size() - 1][j];
          }
  
          for(int i = triangle.size() - 2; i >= 0; --i) {
              for(int j = triangle[i].size() - 1; j >= 0; --j) {
                  path[i][j] = min(path[i+1][j+1], path[i+1][j]) + triangle[i][j];
                  // cout << path[i][j] << " ";
              }
              // cout << endl;
          }
          return path[0][0];
      }
  };