三角形的最短路径

一个三角形，找出从上到下最小路径和，每一步只能移动到下一行相邻的节点。

例如：

           1 

      5        4

    6    2      7 

4     1     8       3

最小路径为1+4+2+1 = 8

输入一个vector数组，输出最小值的和

 

思路：我们从倒数第二层开始，向上进行遍历，每次与其相邻的数进行相加，找出最小的一个

dp[i][j] = min(dp[i+1][j] , dp[i+1][j+1] + min_sum[i][j])

dp表示最小路径，dp[i][j] 表示（i，j）的最小路径和

这样从下向上遍历，最后[0][0]节点就是最小路径的和。

class Solution
{
    class:
        int Sum_min(vector<vector <int>> &sum_min)
        {
            int line = sim_min.size();
            for(int i<line - 2;i>0;i++)
            {
                for(int j = 0;j < i;j++)
                {
                    sum_min[i][j] += min(sum_min[i+1][j],sum_min[i+1][j+1]);
                }
            }
            return sum_min[0][0];
        }
};

代码中没有开辟辅助空间，直接在原数组中进行修改，所以是

dp[i][j] += min(dp[i+1][j],dp[i+1][j+1]);

 道理都是一样的，理解了思路，最重要的是能把思路写出来，这并不容易。