数字三角形

动态规划-----数字三角形

如图所示的数字三角形，请编写一个程序计算从顶到底的一条路径（路径是指上一层的一个数字到下一层两个数字连线的任一条），并找出数字和最大的路径。输出该最大路径数字和，并输出路径。

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

 输出：30 [ 7  3  8  7  5 ]

源码

#include <stdio.h>
#include <math.h>
#define LENGTH 15

int returnmax(int a,int b)
{
    return (a > b ? a : b);
}

int digitalTriangle(int P[],int D[])
{
    int max, level, pointlevel, i, j, left, right;
 int DTemp[LENGTH]={-1};
    int P1[LENGTH]; /**//* 记录每个点的最大路径和 */
    max = 0;
    level =(-1 + sqrt(1 + 8 * LENGTH)) / 2; /**//* 计算共有多少层 */
    for(i = 0; i < LENGTH; i++)
        P1[i] = 0;

    for(pointlevel = 1; pointlevel <= level; pointlevel++)     /**//* 计算每个节点的权值 */
    {
        //pointlevel = i;   /* 定义节点的层 */
        left = (pointlevel) * (pointlevel - 1) / 2;
        right = left + pointlevel - 1;        /**//* 定义三角形边上的点 */

        for(j = left; j <= right; j++)
        {
            if(j == left)  /**//* 处理左边节点 */
   {
    P1[j] = P1[j - pointlevel + 1] + P[j];
    D[j]=j-pointlevel+1;     //记录下一跳
   }
            else if(j == right)  /**//* 处理右边节点 */
   {
                P1[j] = P1[j - pointlevel] + P[j];
    D[j]=j-pointlevel+1;     //记录下一跳
   }
            else             /**//* 处理中间节点 */
   {
    P1[j] = returnmax(P1[j - pointlevel + 1], P1[j - pointlevel]) + P[j];
    if(P1[j-pointlevel+1]>P1[j - pointlevel])
     D[j]=j-pointlevel+1;
    else
     D[j]=j - pointlevel;
   }
        }
    }
   
    for(i = 0; i <= level; i++)
        max = returnmax(max,P1[LENGTH - 1 - level + i]); /**//* 挑选最大的路径和 */
 
 //获取最大值的位置,然后根据位置确定路径
 for(i=0;i<LENGTH;i++)
  if(max==P1[i]) break;
 int pos=i;   //记录下位置
 i=0;
 while(D[pos]!=0)
 {
  //记入DTemp数组
  DTemp[i++]=D[pos];
  D[pos]=D[D[pos]];
 }
 printf("%d ",max);   //输出最大值
 printf("[");
 printf("%d ",P[0]);
 for(j=i-1;j>=0;j--)
  printf("%d ",P[DTemp[j]]);
 printf("%d",P[pos]);
 printf("]");
    return max;
}
          
int main()
{
    int i;
    int A[LENGTH],D[LENGTH];
    int maxsum;
    printf("Please input 15 numbers: ");
    for(i = 0; i < LENGTH; i++)
        scanf("%d",&A[i]);
 for(i=0;i<LENGTH;i++)
  D[i]=0;
    maxsum = digitalTriangle(A,D);
    return 0;
}