如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。n为数塔的层数。

解题思路：
这是一道经典的动态规划问题，我们可以从底层开始往上推导。设f(i,j)表示第i行第j列的位置到底层的最大路径和，则有状态转移方程：
f(i,j) = max(f(i+1,j),f(i+1,j+1)) + a(i,j)，其中a(i,j)表示第i行第j列的值。

最终答案即为f(1,1)。

代码实现：

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

const int N = 1010;
int a[N][N];
int f[N][N];

int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= i; j++)
cin >> a[i][j];

for(int i = n; i >= 1; i--)
for(int j = 1; j <= i; j++)
f[i][j] = max(f[i+1][j], f[i+1][j+1]) + a[i][j];

cout << f[1][1] << endl;

return 0;
}