简单说下题意：已知多个数字组成一个三角形，从顶点开始，对角地下移，一直到底层，形成一条路径，对该路径上所有元素求和，求这个和Sum最大是多少。
/*动态规划求解。算法复杂度为O(n)。 */ #include <iostream> using namespace std; const int MAX = 5055; int arr[MAX]; //用一维数组存储三角形的元素值 int dp[MAX]; //存储以该点为顶点的三角形的Sum最大值 int max(int a, int b) { return a > b ? a : b; } int main() { int n; cin >> n; /*初始化*/ int total = n * (n + 1) / 2; for(int i = 0; i < total; i++) { cin >> arr[i]; } /*对于底层的元素，以其为顶点的三角形的Sum的最大值即为自身*/ for(int i = total - 1; i > total - 1 - n; i--) dp[i] = arr[i]; int nElem = n - 1; //倒数第二层具有的元素数目 /*从倒数第二层的元素开始，往前计算dp*/ for(int i = total - 1 - n; i >= 0; i -= nElem, nElem--) { for(int j = i; j > i - nElem; j--) { /*状态方程，取在该点对角下面的两个点中数值较大的点与自身相加*/ dp[j] = arr[j] + max(dp[j + nElem], dp[j + nElem + 1]); } } /*dp[0]即存储了以顶点的Sum的最大值*/ cout << dp[0] << endl; return 0; }
