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 is11(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的元素，以此类推。

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

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

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

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

class Solution {
public:
	int minimumTotal(vector<vector<int> > &triangle) {

		if(triangle.empty()) return 0;

		//初始化
		vector<int > 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];
    }
};

总结：

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

2014-2-17 update

之前分析了那么多，现在不用那么多分析了，高手可以连打带消地处理特殊情况，代码就更加简练了，O(∩_∩)O哈哈~

直接给出更加简洁的代码--看，无特殊情况处理，即使triangle是空，还是可以准确地返回答案：

//2014-2-17 update
	int minimumTotal(vector<vector<int> > &triangle) 
	{
		int *table = new int[triangle.size()+1];
		for (int i = 0; i <= triangle.size(); i++) table[i] = 0;

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

处理一个特殊情况：

//2014-2-17 update
	int minimumTotal(vector<vector<int> > &triangle) 
	{
		if (triangle.empty()) return 0;
		vector<int> table(triangle.back());
		for (int i = triangle.size() - 2; i >= 0 ; i--)
		{
			for (int j = 0; j < triangle[i].size(); j++)
			{
				table[j] = triangle[i][j] + min(table[j], table[j+1]);
			}
		}
		return table[0];
	}

除了画图分析之外，还要做到“心中有剑”，写出更加简练的代码。