120. 三角形最小路径和-7月14日

题目

120. 三角形最小路径和

我的思路

首先很自然想到深搜和广搜，不过时间复杂度应该相对比较高，2^n，深搜可以用递归实现，广搜可以借助一个队列实现。

 

然后想到用动态规划，可是没有找到从上往下递推的状态转移方程（比如抵达第n级的最小路径和与抵达n-1级或者更小的最短路径和之间的关系）。因为可能存在某条路径在n-1级之前都不是最短路径和。

 

又想办法找反方向从下往上的递推方程。同样相邻或者不同两级到最底层的最短路径没有什么关联。不过在思考的时候发现：如果知道第n级相邻两个节点到最后一级的最短路径和，那么第n-1级与这两个节点有连接的节点到达最底层的最短路径会经过两个节点的路径较小的那一个。基于这个思想从上往下或者从下往上递推都可以，并且空间复杂度为n，只需要一个大小为n的辅助数组存储当前推导的层的每个节点到最低层的最短路径和或者最顶层到当前层每个节点的最短路径和。

 

从下往上递推比从上往下递推少一次求数组中最小元素的过程。

状态转移公式是：P[i] = min(P[i],P[i+1]) + Triangle[j][i]

我的实现

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> shortestPathSum(triangle.size()+1,0);
        printf("triangle.size:%d
",triangle.size());
        for(int i=triangle.size()-1;i>=0;i--){
            for(int j=0;j<triangle[i].size();j++){
                shortestPathSum[j]=min(shortestPathSum[j],shortestPathSum[j+1])+triangle[i][j];
            }
        }
        return shortestPathSum[0];
    }
};


/*
1.首先很自然想到深搜和广搜，不过时间复杂度应该相对比较高，2^n，深搜可以用递归实现，广搜可以借助一个队列实现。
2.然后想到用动态规划，可是没有找到从上往下递推的状态转移方程（比如抵达第n级的最小路径和与抵达n-1级或者更小的最短路径和之间的关系）。因为可能存在某条路径在n-1级之前都不是最短路径和。
3.又想办法找反方向从下往上的递推方程。同样相邻或者不同两级到最底层的最短路径没有什么关联。不过在思考的时候发现：如果知道第n级相邻两个节点到最后一级的最短路径和，那么第n-1级与这两个节点有连接的节点到达最底层的最短路径会经过两个节点的路径较小的那一个。基于这个思想从上往下或者从下往上递推都可以，并且空间复杂度为n，只需要一个大小为n的辅助数组存储当前推导的层的每个节点到最低层的最短路径和或者最顶层到当前层每个节点的最短路径和。
11
9,10
7,6,10
*/

拓展学习