else {i--;D[i] = A[i][k];}
}果:\n");
for(i = 0;i<N;i++)
printf("%d\t",D[i]);
return 0;
}
C[i][j] =0;
}
else {B[i][j] = B[i-1][j]+A[i][j];C[i][j] = 1;}
}
}
//输出数据表和状态表
printf("B表的结果:\n");
for(i = 0;i<N;i++){
for(j = 0;j<=i;j++)
printf("%d\t",B[i][j]);
/*数字塔-数字三角形问题-动态规划算法练习
功能：给定一个由N行数字组成的数字三角形，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大，以及路径。
作者：猪来投胎
时间：2012-7-10
*/
#include<stdio.h>
#define N 4
int main()
{
int A[N][N],B[N][N]={0},C[N][N]={0},D[N];//B存放数据，C存放状态，D存放路径
M = B[N-1][j];
k = j;
}
}
printf("最大的数是:%d,下标是%d,%d\n",M,N-1,k);
//根据状态表C，找路径
D[N-1] = A[N-1][k];
for(i=N-1;i>0;){
if(C[i][k]==0) {i--;D[i] = A[i][--k];}//对角线
int i,j;
int M,k;
//输入数据
for(i = 0;i<N;i++){
for(j = 0;j<=i;j++)
scanf("%d",&A[i][j]);
}
//数字塔数据处理
B[0][0]=A[0][0];
C[0][0]=0;
for(i = 1;i<N;i++){
B[i][0] = B[i-1][0]+A[i][0];
printf("\n");
}
printf("C表的结果:\n");
for(i = 0;i<N;i++){
for(j = 0;j<=i;j++)
printf("%d\t",C[i][j]);
printf("\n");
}
//找出最大值
M = B[N-1][0];
for(j = 1;j<N;j++){
if(B[N-1][j]>M){
C[i][0] = 1;
}
for(i = 1;i<N;i++){
B[i][i] = B[i-1][i-1]+A[i][i];
C[i][i] = 0;
}
for(i = 2;i<N;i++){
for(j = 1;j<i;j++){
if(B[i-1][j-1]>B[i-1][j]){
B[i][j] = B[i-1][j-1]+A[i][j];