题解 | 三角形最小路径和

三种解法：

（1）递归（超时）

 int minroad(vector<vector<int> >& triangle, int i, int j)
     {
         if(i==(triangle.size()-1)) return triangle[i][j];
         else
             return triangle[i][j] + min(minroad(triangle,i+1,j), minroad(triangle,i+1,j+1));   
     }

     int minTrace(vector<vector<int> >& triangle) {
         return minroad(triangle,0,0);
     }

如果采用递归的方法，深度遍历每条路径，存在大量重复计算，时间复杂度为O(2^n)。

（2）递归形式的动态规划

     int minroad(vector<vector<int>> &triangle, vector<vector<int>> &minsum, int i, int j)
     {
         if(minsum[i][j]!=-1) return minsum[i][j]; 
	     if(i == triangle.size()-1) minsum[i][j] = triangle[i][j];
	     else
	     {
		     minsum[i][j] = triangle[i][j] + 					                     min(minroad(triangle,minsum,i+1,j),minroad(triangle,minsum,i+1,j+1));
	     }
	     return minsum[i][j]; 
     }
     int minTrace(vector<vector<int> >& triangle) {
         vector<vector<int>> minsum;
	   // 将minsum中的值全部置为-1
         for(auto iter=triangle.begin();iter!=triangle.end();iter++)
         {
             minsum.push_back(vector<int> (iter->size(),-1));
         }
         return minroad(triangle,minsum,0,0);
     }

每算出一个minroad就保存在minsum[i][j]里面，避免重复计算。

（3）递推形式的动态规划

    int minTrace(vector<vector<int> >& triangle)
    {
        for(int i = triangle.size() - 2; i >= 0; i-- )
        {
            for(int j = 0; j < triangle[i].size(); j++)
            {
                triangle[i][j] += min(triangle[i+1][j],triangle[i+1][j+1]);
            }
        }
        return triangle[0][0];
    }

自底向上。