路径选择的dp问题之三角形最小路径和

原文链接：https://blog.csdn.net/xdzhangzhenhao/article/details/81356095
http://www.cnblogs.com/shizhh/p/5302852.html 动态规划

  1. 三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分.暂时没想到。。。（可能是用in-place方法）可行。

这道题类似于hmm的路径中选择概率最大的乘织。
采用topdown的dp 方法，最顶端的点决定于左右下方两侧的点的minsum，不能采用bottomup的方法。因为可能出现local最优值。
思路是经过当前节点的最小路径为左右节点的路径的最小值加自身，从上往下递归（top down），如果从下往上选，这个思路将是错的，因为你的局部最小并不可以确定最优会经过这里，所以从源头定点开始。
采用递归的方法构造，minsum(trangle, 0, 0).
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution1 {
 
private:
 
	vector<vector<int>> memo;
	//cache
	int m;		// 行数
 
	// i,j代表当前节点的索引
	int minPathSum(vector<vector<int>>& triangle, int i, int j) {
 
		if (i == m - 1)
			return triangle[i][j];
 
		// 相同结构子问题的递归
		if (memo[i][j] == -1) {
			memo[i][j] = min(minPathSum(triangle, i + 1, j), minPathSum(triangle, i + 1, j + 1)) + triangle[i][j];
			cout <<"memo["<<i<<"]["<<j<<"] : "<< memo[i][j] << endl;
		}
		
		return memo[i][j];
	}

public:
	int minimumTotal(vector<vector<int>>& triangle) {
 
		if (triangle.size() == 0)
			return 0;
 
		// triangle中应该都是正数吧
		int res;
		m = triangle.size();
		//构造cache容器
		for (int i = 0; i < m; i++) {
			vector<int> tmp(triangle[i].size(), -1);
			memo.push_back(tmp);
		}
 
		res = minPathSum(triangle, 0, 0);
		return res;
	}
};

//犹记得当日的nlp课程的hmm状态转移方法，yangsky算法，一个句子在一个概率字典里找出最有可能的点。当时查找路径。