给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
思路：自底向上的动态规划，从三角形倒数第二行开始看， triangle[i][j] 一定会到达 triangle[i+1][j] 或者 triangle[i+1][j+1] 得出状态转移方程，
所以当前状态最小和就是 triangle[i+1][j] 与 triangle[i+1][j+1] 的最小值加上 triangle[i][j]
得出状态转移方程： triangle[i][j] = min(triangle[i+1][j],triangle[i+1][j+1]) + triangle[i][j]
简单来说：数组中元素的变化
2
3，4
6，5，7
4，1，8，3
对6来说肯定选4和1的最小值与它相加，对5来说肯定选1与8的最小值与它相加，对7来说肯定选8与3的最小值与它相加所以变成
2
3，4
7，6，10
4，1，8，3
同理：
2
9，10
7，6，10
4，1，8，3
2与9与10的最小值相加为11，即返回11. 可以得出的遍历行和列，所以算法复杂度O(N^2);
1 #define min(a,b) (a < b ? a : b)
2
3 int minimumTotal(int** triangle, int triangleSize, int* triangleColSize)
4 {
5 int i,j;
6 if(triangle == NULL)
7 {
8 return 0;
9 }
10
11 for(i = triangleSize-2;i>=0; i--)
12 {
13 for(j = 0; j < triangleColSize[i]; j++)
14 {
15 triangle[i][j] = min(triangle[i+1][j],triangle[i+1][j+1]) + triangle[i][j];
16 }
17 }
18 return triangle[0][0];
19 }
DP:三角形的最小路径和
原文：https://www.cnblogs.com/ZhengLijie/p/12603350.html
