LeetCode Triangle Bounus达成动态规划法解法

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.

我觉得题目需要解析一下。

就是一条寻路的问题，下标为0的，只能跳到下一行下标为0或1的元素。下标为1的只能跳到下一行下标为1或2的元素，以此类推。

题目说的并不清楚，应该给多两个列子。

看了看网上的其他一些算法，有些算法感觉太繁琐了，不太正规。

我个人觉得这道题不应该想其他解法了。正规解法应该是动态规划法了。不能用贪心法了，因为要全局最优解，而贪心法一般只考虑局部最优解。

我觉得有一个规律可以总结的：

大凡感觉可以用贪心法，而又不能的时候，就要考虑动态规划法了！

要达成Bonus并不难，我的算法准确来计算应该要使用了n-1个额外空间。

而且值得指出的就是这里只是使用了“阉割”了的动态规划法，因为动态规划法还可以准确地求出经过的路径点。

动态规划法的名字就daunting，给人很高深的感觉，如果说蛮力法和贪心法是少林长拳和罗汉拳这样的基本功，那么动态规划法听起来就像是独孤九剑这样的高级功法了，这里只用破刀式就够了，专破田伯光快刀O(∩_∩)O~

下面是详细注释的程序，仔细看一看会知道主程序段只有那么几句，比较简单了：

class Solution {  
public:  
    int minimumTotal(vector > &triangle) {  
  
        if(triangle.empty()) return 0;  
  
        //初始化  
        vector cost;  
        auto iter = triangle.end() - 1;  
  
        //一个元素需要特殊处理  
        if(iter == triangle.begin())  
        {  
            return (*iter)[0];  
        }  
  
        //注意分配内存给vector，然后再使用。不要使用reserve。  
        int n = (*iter).size();  
        cost.resize(n-1);  
  
        //不需要填写最后一个元素  
        for(int i = 0; i< (*iter).size()-1; i++)  
        {  
            cost[i] = min((*iter)[i+1], (*iter)[i]);  
        }  
          
        iter--;  
  
        //特殊情况处理完，进入主程序段  
        for(; iter != triangle.begin(); iter--)  
        {  
            for(int i = 0; i < (*iter).size()-1; i++)  
            {  
                cost[i] = min((*iter)[i]+cost[i], (*iter)[i+1]+cost[i+1]);  
            }  
        }  
  
        return cost[0] + triangle[0][0];  
    }  
};

总结：

主程序段就那么几句，但是作特殊情况处理却花费了大部分的代码，看来特殊情况处理作为一个人编程水平高低的衡量标准之一也不过分！

LeetCode Triangle Bounus达成 动态规划法解法