LeetCode之“动态规划”：Triangle

　　题目要求：　

　　Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

　　For example, given the following triangle

 [

      [],

     [,],

    [,,],

   [,,,]

 ]

　　The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

　　Note:
　　Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

　　具体代码如下：

 class Solution {

 public:

     int minimumTotal(vector<vector<int> > &triangle) {

         int rows = triangle.size();

         if(rows == )

             return ;

         int * dp = new int[rows];

         int szOfLastRow = triangle[rows - ].size();

         for(int i = ; i < szOfLastRow; i++)

             dp[i] = triangle[rows - ][i];

         for(int i = rows - ; i > -; i--)

         {

             int cols = triangle[i].size();

             for(int j = ; j < cols; j++)

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

         }

         return dp[];

     }

 };

　　这个程序中最核心的地方在：

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

　　可以用图表示如下：

　　其中一个例子就是：

　　需要注意的就是这个例子中只改变的是dp[0]，dp[1]并没有改变。

巴特西

LeetCode之“动态规划”：Triangle

最新文章

热门文章