LeetCode题目:Triangle,动态规划

By | 2012 年 10 月 31 日

逐行扫描,计算在每一个位置能取得的最小sum,实际上是该元素上面两个能取得的最小sum中最小的那一个sum加上自己的值。
动态规划,只需要开一个数组重复利用就行了。



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

[
     [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.



代码:40ms过大集合

class Solution {
public:
    int minimumTotal(vector > &triangle) {
        int rows = triangle.size();
        if(0 == rows) return 0;
        int *minSums = new int[rows];
        int *temp = new int[rows];
        
        for(int r = 0; r < rows; ++r) {
            vector trow = triangle[r];
            if(trow.size() != r + 1) return 0;//input error occur
            //first should be last 0 add trow[0]
            temp[0] = trow[0] + (r > 0 ? minSums[0] : 0);
            //from 1 to r - 1, the min from above to parants add self
            for(int i = 1; i < r; ++ i) {
                temp[i] = trow[i] + min(minSums[i-1],minSums[i]);
            }
            //last element, just like the first one. only can add self to the last element above.
            if(r > 0)
                temp[r] = trow[r] + minSums[r-1];
            //swap temp with minSums
            int *tswap = temp;
            temp = minSums;
            minSums = tswap;
        }
        
        //scan the minSums, find out the minimum one
        int m = minSums[0];
        for(int i = 1; i < rows; ++i) {
            if(minSums[i] < m)
                m = minSums[i];
        }
        
        delete temp;
        delete minSums;
        return m;
    }
};



Code rewrite at 2012-12-30

class Solution {
public:
    int minimumTotal(vector > &triangle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int levels = triangle.size();
        if(levels<=0) return 0;
        vector *psum = new vector(levels,0);
        vector *psumtemp = new vector(levels,0);
        (*psum)[0] = triangle[0][0];
        for(int ilevel = 1; ilevel < levels; ++ilevel) {
            vector &level = triangle[ilevel];
            const int levelsize = level.size();
            //only one path could arrive to the first and last number in a level
            (*psumtemp)[0] = (*psum)[0] + level[0];
            //if (level.size() > 1)
            (*psumtemp)[levelsize - 1] = (*psum)[levelsize - 2] + level[levelsize - 1];
            //there are 2 pathes for the middle numbers.
            for(int ipos = 1; ipos < levelsize - 1; ++ipos) {
                int tsum = (*psum)[ipos] + level[ipos];
                if(tsum > (*psum)[ipos-1] + level[ipos]) {
                    tsum = (*psum)[ipos-1] + level[ipos];
                }
                (*psumtemp)[ipos] = tsum;
            }
            //swap the psum and psumtemp
            vector *ptemp = psum;
            psum = psumtemp;
            psumtemp = ptemp;
        }
        //scan the psum and output the minnimum sum
        int minsum = (*psum)[0];
        for(int i = 1; i < levels; ++i) {
            if(minsum > (*psum)[i])
                minsum = (*psum)[i];
        }
        //clearup
        delete psum;
        delete psumtemp;
        return minsum;
    }
};



Code rewrite at 2013-1-17

class Solution {
public:
    int minimumTotal(vector > &triangle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int rows = triangle.size();
        if(0 == rows) return 0;//error
        int *sumrow = new int[rows];
        int *sumrowtemp = new int [rows];
        sumrow[0] = triangle[0][0];
        for(int ir = 1; ir < rows; ++ir) {
            vector &trirow = triangle[ir];
            sumrowtemp[0] = sumrow[0] + trirow[0];
            for(int ic = 1; ic < trirow.size(); ++ic) {
                int minsum = sumrow[ic-1];
                if(ic < trirow.size()-1 && sumrow[ic] < minsum) {
                    minsum = sumrow[ic];
                }
                sumrowtemp[ic] = minsum + trirow[ic];
            }
            int *temp = sumrow;
            sumrow = sumrowtemp;
            sumrowtemp = temp;
        }
        int ret = sumrow[0];
        for(int ic = 1; ic < rows; ++ic) {
            if(ret > sumrow[ic]) ret = sumrow[ic];
        }
        delete sumrow;
        delete sumrowtemp;
        return ret;
    }
};

15 thoughts on “LeetCode题目:Triangle,动态规划

  1. macemers

    楼主你好,

    想请问,两次的code rewrite比起第一次有哪些改进的地方?另外题目有个bonus要O(n)的空间,似乎都没有达到?

    全部解法都是开了两个O(n)的空间的数组

    Reply
    1. uniEagle Post author

      算法上本身没有什么改进,只在循环次数和边界上稍有变化。最开始那个版本是整个三角循环的,后面两次都是从第二行开始的。
      另外其实常数倍O(n)还是O(n)。

      Reply
      1. macemers

        题目上写“using only O(n) extra space, where n is the total number of rows in the triangle.”

        难道不是指,只用一个长度为n的数组吗?

        Reply
  2. haiyyang

    根据你开头动归的提示,我的代码是这样的,嘿嘿 :

    class Solution {
    public:
        int minimumTotal(vector &triangle) {
            if(triangle.empty())return 0;
            
            int max=triangle.back().size();
            vector dp(triangle.back().begin(),triangle.back().end()); //最后一行拷贝到额外空间,并作为动态规划的表格
            
            for(int i=triangle.size()-2;i>=0;i--)
            {
                int s=triangle.at(i).size();
                for(int j=0;j
    

    Reply
  3. Will

    能否请教下这个的时间复杂度是不是O(n^2)? n为rows 如果n为一共多少个数的话,应该是O(n)。
    那能否用找出每行的最小值,然后从而遍找到path的方法呢?
    谢谢!!!

    Reply
    1. uniEagle Post author

      恩,如果按照题目中n定义为总的行数的话,时间复杂度是O(n^2)的。
      找出每行最小,加起来的方法不正确,如果你看这棵树的话就知道了:

      [
           [2],
          [3,4],
         [6,5,2],
        [1,5,8,3]
      ]
      

      这棵树的最小值并不是(2+3+2+1 = 8)

      Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注