和POJ3176几乎一模一样，（只有row的范围不同，其实可以不用改的，我还是改了一下），连给的数据都一样，都是最简单的那个 dp 动归问题
AC的代码：
#include<stdio.h>int dp[102][102];inline int max(int a,int b){return a>b?a:b;}int main()
{int n,i,j;scanf("%d",&n);//输入for(i=1;i<=n;i++)for(j=1;j<=i;j++)scanf("%d",&dp[i][j]);//dpfor(i=n-1;i>=1;i--)for(j=1;j<=i;j++)dp[i][j]=max(dp[i][j]+dp[i+1][j],dp[i][j]+dp[i+1][j+1]);printf("%d\n",dp[1][1]);return 0;
}
转过来一个写的还不错的贴
问题描述：输入一个数字三角形
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(Figure 1)
如Figure 1所示一样，在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都是能往左下或右下走。只需要求出最的和即可，不需要输出路径。
解题思路：算法一 、递归思想
设f(i,j) 为三角形上从点(i,j)出发向下走的最长路经，则 f(i,j) =max(f(i 1,j), f(i 1,j 1))
要输出的就是f(0,0)即从最上面一点出发的最长路经。
以D(r, j)表示第r行第 j 个数字，以MaxSum(r, j) 代表从第 r 行的第 j 个数字到底边的各条路径中，数字之和最大的那条路径的数字之和，则本题是要求MaxSum(0,0)。（假设行编号和一行内数字编号都从0开始)。
典型的动态规划问题。
从某个D(r, j)出发，显然下一步只能走D(r 1,j)或者D(r 1, j 1)，所以，对于N行的三角形：
if ( r == N-1 )
MaxSum(r,j) = D(N-1,j)
else
MaxSum(r, j) = Max(MaxSum(r 1,j),MaxSum(r 1,j 1) ) D(r,j);
代码如下：
#include <iostream.h>
#define MAX 101
int triangle[MAX][MAX];
int n;
int longestPath(int i, int j);
void main(){
int i,j;
cin >>n;
for(i=0;i<n;i)
for(j=0;j<=i;j )
cin>> triangle[i][j];
cout <<longestPath(0,0) << endl;
}
int longestPath(int i, int j){
if(i==n-1)return triangle[i][j];
int x =longestPath(i 1,j);
int y =longestPath(i 1,j 1);
if(x<y) x=y;
return x triangle[i][j];
}
（超时！！！！）
为什么会超时呢？
答：如果采用递规的方法，深度遍历每条路径，存在大量重复计算，则时间复杂度为 2n，对于 n = 100，肯定超时。
一种可能的改进思想：从下往上计算，对于每一点，只需要保留从下面来的路径中和最大的路径的和即可。
因为在它上面的点只关心到达它的最大路径和，不关心它从那条路经上来的。
问题：有几种解法？？
从使用不同的存储开销角度分析
2?00?00譻izeof(int)
(100?00 100)譻izeof(int)
100譻izeof(int)
解法一、
如果每算出一个MaxSum(r,j)就保存起来，则可以用o(n2)时间完成计算。因为三角形的数字总数是n(n 1)/2
此时需要的存储空间是：
int D[100][100]; //用于存储三角形中的数字
int Sum[100][100]; //用于存储每个MaxSum(r,j)
解法二、
没必要用二维Sum数组存储每一个MaxSum(r,j),只要从底层一行行向上递推，那么只要一维数组Sum[100]即可,即只要存储一行的MaxSum值就可以。比解法一改进之处在于节省空间，时间复杂度不变。
解法三、
能否不用二维数组D[100][100]存储数字呢？
思路：倒过来考虑。前面的思路是从底往上最终算出MaxSum(0,0)。如果从顶往下算，最终算出每一个MaxSum(N-1,j)，然后再取最大的MaxSum(N-1,j)，不就是答案吗？此时递推公式为：
if( r == 0 )
MaxSum(r,j) = D[0][0];
else
MaxSum(r,j) = Max(MaxSum(r-1,j-1), MaxSum(r-1,j)) D[r][j];
由于两重循环形式为：
for( r = 0 ; r < N ; r )
for( j = 0 ; j < r 1 ; j ) {
………..
}
r,j不断递增，所以实际上不需要D[100][100]数组，每次从文件里读取下一个数字即可。
而每一行的每个MaxSum(r,j)仍然都需要存储起来，这样，只需要一个Sum[100]数组。
(注：只需设一个临时存储变量，在计算MaxSum(r,j)后写入数组时，暂存MaxSum(r-1,j))
解法四：
也就是本人所执行的算法，它是基于解法三中“从上往下”的思想，每输入一个数后临时存起来，然后用一个sum[i]来存放该处的最大路径和数，由于所输入的数字三角是成一个以1为公差的等差数列，充分利用其变量间的一种亲密关系，成功实现并不困难。具体的算法如下：
#include <iostream>
using namespace std;
int main(){
int sum[5051]={0}; //声明用来存放数据的数组，sum=(n^2+n)/2 max(sum)=5050(n==100)
int n,r,j,num,i=1,max=0; //r表变化的行数，
cin>>n; //输入数据行数
for(r=1;r<=n;r++){
for(j=1;j<=r;j++,i++){
scanf("%d",&num); //输入三角形数据
if(j==1){sum[i]=num+sum[i-r+1];continue;} //输入的是每行的第一个数
if(j==r)sum[i]=num+sum[i-r]; //输入的是每行中的最后一个数
else sum[i]=(sum[i-r]>sum[i-r+1]?sum[i-r]:sum[i-r+1])+num; //输入的是中间数时
}
}
/*for(j=1;j<i;j++)cout<<sum[j]<<""; //测试用来输出每个点上所对应的最大路径和数
cout<<endl;
*/
for(j=1;j<i;j++) //寻最大路径和数
if(sum[j]>max)max=sum[j];
cout<<max<<endl;
system("pause");
return 0;
}
心得：经过解此题，让我走出了一个算法的局限误区，思维进一步得到了提高，之前遇到一个类似的题，当初就受思维的局限心想要用到搜索，或者是有关图的遍历才能解决的问题，没想到如今却只要区区几十行代码就解决了。“规律往往是掌握在有一双“狠”的眼睛的人的大脑里！”从而得出了这样一句话来收场。