算法训练 数字三角形

经过这一阵努力的学习，我的C＋＋基础总算学完了，可以开始自己刷题了，前天朋友给了我几道题，让我帮他看看，我也是很兴奋，跃跃欲试，可是我看到题时，我傻眼了，在我之前做过这道题，可是我没有做出来，怎么办？
其实我没有想怎么办，只是当机立断的接了下来，因为我是个很逗比的人，自己遇见很难得题，就懒得去多想，可是当别人问我时，虚荣的我就会绞尽脑汁去思考，有了压力，我的大脑也更加活跃，总是可以解决我本以为自己解决不了的问题。于是，我就跟朋友说，交给我吧，等我有时间了尽快给你答复。
接着，我就开始对这道题展开了新一轮的攻势……

问题描述：

                                    7
                                 3     8 
                              8     1     0 
                           2     7     4     4 
                        4     5     2     6     5

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每一条路径，把路径上的数字加起来可以得到一个和，和的最大路径称为最佳路径。你的任务就是求出最佳路径上的数字和。
注意：路径上的每一步只能从一个数走到下一层上和它最邻近的左边的数或者右边的数。

输入格式
文件中首先读到的是三角形的行数。
接下来描述整个三角形

输出格式
最大总和（整数）

样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

样例输出
30

#include <stdio.h>
int main(int argc, const char * argv[])
{
    int SanJiaoXing[5050]={0},Sum[5050]={0},n=0,i=0,j=0;
    scanf("%d",&n);
    for (; i<(1+n)*n/2; i++)
    {
        scanf("%d",&SanJiaoXing[i]);
    }
    for (i=n*(n-1)/2; i<(1+n)*n/2; i++)
    {
        Sum[i]=SanJiaoXing[i];
    }
    j=n-1;
    for (i=n*(n-1)/2-1; i>=0; i--)
    {
        if ((j+1)*j/2-1-i==j)
        {
            j--;
        }
        Sum[i]=SanJiaoXing[i]+(Sum[i+j]>Sum[i+j+1]?Sum[i+j]:Sum[i+j+1]);
    }
    printf("%d\n",Sum[0]);
    return 0;
}

这个方法虽然是做出来了，但是做过这个题后我感觉代码真心好难理解，直观性很差，别人看会很难看懂，于是我就又改写了代码，把一维数组改为二维数组做了一遍，结果依然正确，挺好的。但是这两种办***所占的内存和时间差距不大，所以依个人感觉，用二维数组解题会比用一维数组更加好点，因为代码更加直观。代码如下：

#include <stdio.h>
int main()
{
    int SanJiaoXing[100][100]={0},Sum[100][100]={0};
    int n=0,i=0,j=0;
    scanf("%d",&n);
    for (; i<n; i++)
    {
        for (j=0; j<=i; j++)
        {
            scanf("%d",&SanJiaoXing[i][j]);
        }
    }
    for (i=0; i<n; i++)
    {
        Sum[n-1][i]=SanJiaoXing[n-1][i];
    }
    for (i=n-2; i>=0; i--)
    {
        for (j=0; j<=i; j++)
        {
            Sum[i][j]=SanJiaoXing[i][j]+(Sum[i+1][j]>Sum[i+1][j+1]?Sum[i+1][j]:Sum[i+1][j+1]);
        }
    }
    printf("%d\n",Sum[0][0]);
    return 0;
}    

　　最后，送给自己一句话：成就感来源于克服困难！(☆_☆)