数字三角形是一个由非负数组成的三角形,第n行有n个数,形如:
1
2 3
4 5 6
除最下行之外,每一行的左下和右下各有一个数,从第一行开始,向下,左或者右走一格,直到走到最后一行,所经过的路径上的数的和最大
除了简单的递归运算:
int d(int i,int j){
return a[i][j]+(i==n?0:d(i+1,j)>?d(i+1,j+1));
}
以及递推运算:
int i,j;
for(j=1;j<=n;j++)
d[n][j]=a[n][j];
for(i=n-1;i>=1;i--)
for(j=1;j<=i;j++){
d[i][j]=a[i][j]+d[i+1][j]>?d[i+1][j+1];
}
还可以用记忆化搜索的方法,减少计算量,记忆化搜索的方法定义一个数组d,d初始化值全部为-1,然后再编写递归函数,如果发现d[i][j]的值已经被计算过了,就直接返回:
#include "stdio.h"
#include "memory.h"
int d[100][100];
int a[100][100];
int n;
int b(int i,int j){
if (d[i][j]>=0) return d[i][j];
if (i!=n)
{
int temp=b(i+1,j)>b(i+1,j+1)?b(i+1,j):b(i+1,j+1);
d[i][j]=a[i][j]+temp;
}
else{
d[i][j]=a[i][j];
}
return d[i][j];
}
void main(){
memset(a,0,100*100*sizeof(int));
memset(d,-1,100*100*sizeof(int));
scanf("%d",&n);
for(int i=0;i<n;i++){
for (int j=0;j<=i;j++)
{
scanf("%d",&a[i][j]);
}
}
int t=b(0,0);
}