数字三角形递归的一些思考

题目要求：

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

在上面的数字三角形中寻找在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。
　　三角形的行数大于1小于等于100，数字为 0 - 99

输入格式：
5 //三角形行数。下面是三角形
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

递归的程序代码实现：

#include "stdio.h"
#define MAX 100 

int n;    
int D[MAX][MAX];

int main(){
    
    int i,j;
    
    printf("Input N:\n");
    scanf("%d",&n);
    
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=i;j++)
        {
            scanf("%d",&D[i][j]);
        }
        printf("\n");
    }
    
    printf("Max is %d",MaxSum(1,1));
} 

int MaxSum(int i,int j)
{
    if(i==n)
        return D[i][j];
    int x=MaxSum(i+1,j);
    int y=MaxSum(i+1,j+1);
    return max(x,y)+D[i][j];
}

int max(int m,int n){
    return m>n?m:n;
}

之前学的递归的斐波拉契函数和二叉树遍历还可以理解，但这次的三角形递归有的地方一直没想明白，特此把三角形递归的执行过程写了一遍，做到心中有数，其实也都是一个原理。

数字三角形递归的一些思考

其实递归就是多个算法嵌套调用，递归递归，条件没达到时，一直往算法内部递进，直到遇到结束条件再一层一层返回。关键递归必须要有一个结束条件，当程序运行到结束条件时，它就会返回上一层的调用他的递归语句，然后去执行这个递归语句下面的语句。然后运行结束再往上回一层，这样一直往上。

也可以把它的执行过程想象成栈的过程，条件没达到一直压栈，达到了一个个弹栈。

数字三角形递归的一些思考

相关推荐