Leetcode: Triangle (6ms)(Dynamic programming)

PROBLEM:
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

[

     [2],

    [3,4],

   [6,5,7],

  [4,1,8,3]

]

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.

Hide Tags

 Array Dynamic Programming

Analysis:

This is a classical DP problem. 

At first, you should understand the problem correctly: each step you may move to adjacent numbers on the row below. For each number, you have only two options in the next step. 

The first idea is using backtracking. Try all the possible path sum and chose the minimal one. There are two issues with this method. One is that it will use lots of stacks. The other one is that we don't know what the minimal value and we have to try all possible path to identify it (or we don't know what's the constrain to stop).  

The second idea is the DP to avoid the repeating works. See the figure below:

 the numbers in gray are triangle numbers while the black numbers are their possible sum. This figure says how the DP is implemented from top to down. To save previous calculation values, we use an array dp to store them and update them in the next round. For each number in the triangle, they may have two possible sum and we kill the bigger one and leave the smaller one. In the end, we use the smallest one in dp as the return value. 

A little bit better way to implement the DP is to sweep from down to top. But they are basic the same. 

////////////////////////////////////////////////////////////////////////////

//code (8ms)

class Solution {

public:

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

              if (triangle.size() == 0)return 0;

              vector<int> dp, dp_tmp;

              dp.resize((triangle[triangle.size()-1].size()), 0);//defined to be the max length

              for (int i = 0; i < triangle.size(); i++){

                     dp_tmp.assign(dp.begin(),dp.end());

                     for (int j = 0; j < triangle[i].size(); j++){

                           if (j - 1 < 0){//triangle[i][j] is the left most item

                                  dp[j] = triangle[i][j] + dp_tmp[j];

                           }

                           else if (i == j){//triangle[i][j] is the right most item

                                  dp[j] = triangle[i][j] + dp_tmp[j - 1];

                           }

                           else{//triangle[i][j] is the middle

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

                           }

                     }

              }

              //find the minimal value in dp

              int min_tmp=dp[0];

              for (int i = 0; i < dp.size(); i++){

                     if (min_tmp>dp[i]){

                           min_tmp = dp[i];

                     }

              }

              return min_tmp;

       }

};

Revised code for (6ms):
///////////////////////////////////////////////////

class Solution {

 public:

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

               if (triangle.size() == 0) return 0;

               vector<int> dp1 = triangle[0];

               int row = triangle.size();

               for (int i = 1; i<row; i++){

                      vector<int> dp2;

                      dp2.assign(i + 1, 0);

                      for (int j = 0; j<i + 1; j++){

                            if (j == 0) dp2[j] = dp1[j] + triangle[i][j];

                            else if (j == i)dp2[j] = dp1[j - 1] + triangle[i][j];

                            else{

                                   int tmp1 = dp1[j] + triangle[i][j];

                                   int tmp2 = dp1[j - 1] + triangle[i][j];

                                   dp2[j] = tmp1 > tmp2 ? tmp2 : tmp1;

                            }

                      }

                      dp1 = dp2;

               }

               //find min

               sort(dp1.begin(), dp1.end());

               return dp1[0];

        }

 };