（动态规划）给定三角形，找到从上到下的最小路径总和

• 题目：

  给定一个三角形，找到从上到下的最小路径总和。 您可以将每个步骤移动到下面一行中的相邻数字。
  
  例如，给定以下三角形
  
  [
        [2]，
       [3,4]，
      [6,5,7]，
     [4,1,8,3]
  ]]
  
  
  从顶部到底部的最小路径总和为11（即，2 + 3 + 5 + 1 = 11）。
  
  注意：
  奖励点，如果你能够使用只使用O（n）额外的空间，其中n是三角形中的总行数。

• 思路：
  • 第一种解法：这个题目提示是用DP去做。这里一般的思路是使用二维数组去存储每一层与上一层想加的最小值得和。有两种遍历方式，从下到上和从上到下。第一种遍历方式比较简单。第二种方式需要考虑比较多的因素。
  • 代码

    //从上到下遍历
    class Solution {
    public:
        int minimumTotal(vector<vector<int> > &triangle) {
            int row = triangle.size();
            vector<vector<int> > path(row);//申请行空间，二维数组
            for (int i=0; i<row; i++)
                path[i].resize(triangle[i].size(), 0);//申请列空间
            //path[0][0] = triangle[0][0];
            int col = 0;
            for (int i=0; i<row; i++){
                col = triangle[i].size();
                for (int j=0; j<col; j++){
                    if (0 == i)
                        path[i][j] = triangle[i][j];
                    else{
                        if (j == 0)
                            path[i][j] = path[i-1][j] + triangle[i][j];
                        else if (j == (col-1))
                            path[i][j] = path[i-1][j-1] + triangle[i][j];
                        else
                            //当不是首尾数字的时候，看上一层相邻的两个数哪个更小更适合想加
                               path[i][j] = min(path[i-1][j-1], path[i-1][j]) + triangle[i][j];
                    }
                } 
            }
            int Min = path[row-1][0];
            for (int i=0 ;i<path[row-1].size(); i++)
                if (Min > path[row-1][i])
                    Min = path[row-1][i];
               return Min;
        }
    };

    //从下到上遍历
    class Solution {
    public:
        int minimumTotal(vector<vector<int> > &triangle) {
            int row = triangle.size();
            vector<vector<int> > path(row);//申请行空间，二维数组
            int num = 0;
            for (int i=row-1; i>=0; i--)
                path[num++].resize(triangle[i].size(), 0);//申请列空间 
            int col = 0;
            int s = row;
            for (int i=0; i<row; i++){
                s--;
                col = triangle[s].size();
                for (int j=0; j<col; j++){
                    if (0 == i)
                        path[i][j] = triangle[s][j];
                    else{
                        //当不是首尾数字的时候，看上一层相邻的两个数哪个更小更适合想加
                           path[i][j] = min(path[i-1][j], path[i-1][j+1]) + triangle[s][j];
                    }
                } 
            }
               return path[row-1][0];
        }
    };

  • 第二种解法：在原有空间的基础上直接进行运算，不用重新命名空间了。代码比较简洁，但是效率好像不是很高。