问题描述：
从三角形的顶点往下走，只能走自身正下方和右下方的坐标，返回从最顶端到最底下所经过的路径值加起来的最大值。
数据如：
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
最大值为30.
第一种算法：
算法思想：从上往下走，定义一个s二维数组，记录每走一步的最大值，分为三种情况，第一种：列为0时，最大值只与上上方的值有关，直接另s[i][j]等于a[i][j]加s[i-1][j]；第二种：当i = j时，s[i][j]只与a[i-1][j-1]有关，则s[i][j]等于a[i][j]加a[i-1][j-1]；第三种：到达a[i][j]的有两条路，此时在两条里选一个较大的付给s[i][j]。完成后最大值存在s数组的最后一行，进行比较便得出最大值。
代码：
#include <stdio.h>
#define N 5
int max(int m, int n)
{
if (m > n)
return m;
else
return n;
}
int numberTrangle(int a[][N])
{
int s[N][N];
s[0][0] = a[0][0];
int i, j;
for (i = 1; i < N; i++)
{
for (j = 0; j <= i; j++)
{
if (j == 0)
{
s[i][j] = a[i][j] + s[i - 1][j];
}
if (j == i)
{
s[i][j] = a[i][j] + s[i - 1][j - 1];
}
else
{
int m = a[i][j] + s[i - 1][j - 1];
int n = a[i][j] + s[i - 1][j];
s[i][j] = max(m, n);
}
}
}
int max = s[N - 1][0];
for (j = 0; j < N; j++)
{
if (max < s[N - 1][j])
max = s[N - 1][j];
}
return max;
}
int main(void)
{
int a[N][N], i, j;
for (i = 0; i < N; i++)
{
for (j = 0; j <= i; j++)
{
scanf("%d", &a[i][j]);
}
}
printf("%d\n", numberTrangle(a));
return 0;
}
第二种算法：
算法思想：从下往上走，同样定义一个s二维数组，首先令s数组的最后一行等于a数组的最后一行，让s[i][j]和s[i][j-1]分别与a[i-1][j-1]相加比较两者的最大值，令s[i-1][j-1]保存每次经过两个可选路径时的最大值，依次执行，最后s[0][0]保存的即为所有路径的最大值。
代码：
#include <stdio.h>
#define N 5
int max(int m, int n)
{
if (m > n)
return m;
else
return n;
}
int numberTrangle(int a[][N])
{
int s[N][N];
int i, j;
for (i = 0; i < N; i++)
{
s[N - 1][i] = a[N - 1][i];
}
for (i = N - 1; i >= 1; i--)
{
for (j = i; j >= 1; j--)
{
int m = s[i][j] + a[i - 1][j - 1];
int n = s[i][j - 1] + a[i - 1][j - 1];
s[i - 1][j - 1] = max(m, n);
}
}
return s[0][0];
}
int main(void)
{
int a[N][N], i, j;
for (i = 0; i < N; i++)
{
for (j = 0; j <= i; j++)
{
scanf("%d", &a[i][j]);
}
}
printf("%d\n", numberTrangle(a));
return 0;
}
