View Code of Problem 4063

#include<iostream>
#include<string>
#include<algorithm>
#include<stack>
#include<vector>
#include<cmath>

using namespace std;

//动态规划

int main() {
	int n;
	while (cin >> n && n != 0) //注意输入以n=0结束
	{
		int **arr = new int*[n];
		for (int i = 0; i < n; i++)//创建二维动态数组
		{
			arr[i] = new int[i + 1];
			for (int j = 0; j < i+1; j++)
				cin >> arr[i][j];
		}
		for (int i = n-1; i > 0; i--)//从树根开始向上遍历，寻找最小路径
			for (int j = 0; j < i; j++)
				arr[i - 1][j] + arr[i][j] > arr[i - 1][j] + arr[i][j + 1] ? arr[i - 1][j] = arr[i - 1][j] + arr[i][j + 1] : arr[i - 1][j] = arr[i - 1][j] + arr[i][j];
		cout << arr[0][0] << endl;
	}
	return 0;
}