动态规划练习——数字三角形

问题描述：

从三角形的顶点往下走，只能走自身正下方和右下方的坐标，返回从最顶端到最底下所经过的路径值加起来的最大值。

数据如：

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;
}