1.实践题目：数字三角形

问题描述：给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。

2.问题解析：

这其实是一道非常简单的动态规划问题。问题解决办法是建一个表，初值为三角形对应位置的值，之后以填表覆盖的方式，自底向上的把三角形的路径和进行更新。

递归方程为dp[i][j] = max(dp[i−1][j],dp[i−1][j−1])+a[i][j]

3.实现代码：

#includeusing namespace std;int main(){ int n,a[105][105]; int i,j,k=1; int max; cin>>n; for(i=1;ia[i][j]; } } for(i=n-1;i>0;i--) { for(j=n-1;j>0;j--) { if(a[i+1][j]>a[i+1][j+1]) max=a[i+1][j]; else max=a[i+1][j+1]; a[i][j]+=max; } } cout