动态规划经典题目三角形最短路径

给一个三角形数组，求最短路径
例如：

• 从最后一层开始，建立一个n+1长度的dp数组，表示当前层到最底层的最短路径，初始化全为0，从后往前动态规划：当前的dp更新值为（当前位置值+ m i n ( 当 前 位 置 下 一 层 2 个 相 邻 位 置 的 d p 值 ) min(当前位置下一层2个相邻位置的dp值) min(当前位置下一层2个相邻位置的dp值)）
• 绿色值的为更新之后的数值
  

#include
#include
using namespace std;

int main() {
	vector> triangle{ {2},{3,4},{6,5,7},{4,1,8,3} };
	

	int length = triangle.size();
	//cout << length; // 4
	vector dp; //dp数组初始化
	for (int i = 0; i < length+1; i++) {
		dp.push_back(0);
	}

	// 从下往上dp
	for (int i = length - 1; i >= 0; i--) {
		// 从最后一层开始
		for (int j = 0; j < i+1; j++) { // 第i层有i+1个数
			// 从第0个位置开始更新dp数组
			// 当前位置的最小路径值为：当前值+(当前层的下一层相邻的最小值路径值)
			//cout << i << j< 
结果