题目链接： POJ-Cow Bowling
题目大意：
一个三角矩阵， 比如：
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5从三角形的顶端往下沿着对角线走，直到走到底部。求这样一条路径经过的点的分数之和的最大值。
， 输入格式：
第一行一个 N 接下来N行每行就是三角矩阵的一层
输出格式
最大的分数
题解：
最基础的 dp ， dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j] , 其中 a[][] 存储原始的三角形矩阵， dp[1][1] 就是我们最后要求的答案。
代码：
#include <iostream> #define MAXN 350 using namespace std; int dp[MAXN][MAXN]; int a[MAXN][MAXN]; int N; int main() { cin >> N; for (int i = 1; i <= N; i++) for (int j = 1; j <= i; j++) cin >> a[i][j]; for (int j = 1; j <= N; j++) dp[N][j] = a[N][j]; for (int i = N-1; i > 0; i--) { for (int j = 1; j <= i; j++) { dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + a[i][j]; } } cout << dp[1][1] << endl; return 0; }