三角形最小路径和 2种方法 动规

 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

1、自顶向下

对于给定的一组数据，[ [2], [3,4], [6,5,7], [4,1,8,3] ]， 我们用图形表示其转移流程

右边是最终转移的结果，由此我们可以得到状态转移方程：
    $dp[i][j]=triangle[i][j]+min(dp[i-1][j],dp[i-1][j+1])$dp[i][j]=triangle[i][j]+min(dp[i−1][j],dp[i−1][j+1])
    $dp[i][0]=triangle[i][0]+ dp[i-1][0]$dp[i][0]=triangle[i][0]+dp[i−1][0]
    $dp[i][i]= triangle[i][i]+dp[i-1][i-1]$dp[i][i]=triangle[i][i]+dp[i−1][i−1]
$dp[i][j]$dp[i][j]表示以当前元素为结尾的的最短路线，其思想是和求数组的最大子序和定义是类似的，这里我们也要注意两个边界条件，当$dp[i][0]$dp[i][0]时，从上层转移过来的元素只能是$dp[i-1][0]$dp[i−1][0],当$ddp[i][i]$ddp[i][i]时，从上层转移过来的元素只能是$dp[i-1][i-1]$dp[i−1][i−1]。最后遍历dp数组最后一行的元素求出最大值即可。
这里由于我们只要求返回最短路径，所以我们直接在triangle数组上进行运算，最后triangle数组的值的形式就是我们转移的结果图。

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
         /*
         自顶向下
         dp[i][j]=triangle[i][j]+min(dp[i-1][j],dp[i-1][j+1])   
           dp[i][0]=triangle[i-1][0]+ dp[i][0]
           dp[i][i]= dp[i][i]+triangle[i-1][i-1]
         */
         if(triangle.size()==0)
         return 0;
          if(triangle.size()==1)
         return triangle[0][0];
         vector<vector<int>> dp=triangle;
         for(int i=1; i<triangle.size(); i++)
         {
            for(int j=0; j<triangle[i].size();j++)
            {
                if(j==0)
                  triangle[i][j]=triangle[i-1][0]+triangle[i][0];
                else if(j==i)
                  triangle[i][j]=triangle[i][i]+triangle[i-1][i-1];
                else
                  triangle[i][j]=triangle[i][j]+min(triangle[i-1][j-1],triangle[i-1][j]);
            }
         }
         int ret=INT_MAX;
         for(int i=0;i<triangle[triangle.size()-1].size();i++)
         {
              ret=min(ret,triangle[triangle.size()-1][i]);
         }
         return ret;
    }
};

2、从下到上

 当然我们也可以从下到上开始求最短路径，到底什么意思，我们把状态转移方程列出来就懂了。

$dp[i][j]=triangle[i][j]+max(dp[i+1][j],dp[i+1][j+1])$dp[i][j]=triangle[i][j]+max(dp[i+1][j],dp[i+1][j+1])，这样的好处时就不要判断特殊条件，这是我们注意到每个元素都有两个被指向的箭头，分别来自于$triangle[i+1][j],triangle[i+1][j+1])$triangle[i+1][j],triangle[i+1][j+1]).最后直接返回dp[0][0].

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
         /*
         从下到上
         dp[i][j]=triangle[i][j]+max(dp[i+1][j],dp[i+1][j+1])   
         */
         if(triangle.size()==0)
         return 0;
          if(triangle.size()==1)
         return triangle[0][0];
         for(int i=triangle.size()-2;i>=0;i--)
         {
              for(int j=0; j<triangle[i].size();j++)
              {
                  triangle[i][j]=triangle[i][j]+min(triangle[i+1][j],triangle[i+1][j+1]);
             }
         }
          return triangle[0][0];         
    }
};