Dynamic programming classical topic triangle shortest path

Preface

Give an array of triangles , Find the shortest path
for example ：

Ideas

• From the last floor , Build a n+1 Of length dp Array , Represents the shortest path from the current layer to the lowest layer , Initialize all to 0, Dynamic planning from back to front ： Current dp The update value is （ Current position value +$min(WhenfrontpositionSet\; upNextOnelayer2individualphaseadjacentpositionSet\; upOfdpvalue)$）
• The green value is the updated value
  

Sample code

#include<iostream>
#include<vector>
using namespace std;

int main() {
	vector<vector<int>> triangle{ {2},{3,4},{6,5,7},{4,1,8,3} };
	/*for (auto avec : triangle) {
		for (auto num : avec) {
			cout << num << " ";
		}
		cout << endl;
	}*/

	int length = triangle.size();
	//cout << length; // 4
	vector<int> dp; //dp Array initialization 
	for (int i = 0; i < length+1; i++) {
		dp.push_back(0);
	}

	//  From bottom to top dp
	for (int i = length - 1; i >= 0; i--) {
		//  From the last floor 
		for (int j = 0; j < i+1; j++) { //  The first i Layer has a i+1 Number 
			//  From 0 Update started at dp Array 
			//  The minimum path value for the current location is ： Current value +( The adjacent minimum path value of the next layer of the current layer )
			//cout << i << j<<endl;

			dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
		}
	}
	cout << dp[0] << endl; //  Shortest path required 
	//  Print the final dp Array 
	for (auto item : dp) {
		cout << item << " ";
	}

	return 0;
}

result