数字金字塔最大路径和—

数字金字塔最大路径和——递归

题目描述

假设有如下所示的一个数字金字塔，现在，要求写一个程序来查找从顶点到底部任意处结束的路径，使路径经过的数字的和最大，并输出该路径的最大和。比如以下金字塔的和最大路径的和为7+3+8+7+5=30。
7

3 2

8 1 0

2 7 4 4

4 5 2 6 5

 C++ Code 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <iostream>
#include <cmath>

using namespace std;

const int MAXLAYER = 5; // 金字塔的最大层数

/** @brief
* 计算金字塔中第layer层第pos个元素在数组中的下标
*
* @param layer int 金字塔中第layer层
* @param pos int 金字塔中第layer层第pos个元素
* @return int
*
*/
int Index(int layer, int pos)
{
    return layer * (layer - 1) / 2 + pos;
}

/** @brief
* 金字塔自上而下路径中，路径和的最大值
*
* @param pNums int* 存储金字塔中的数字，这里是一维数组，按层次顺序进行存储
* @param layer int 金字塔中的第layer层[1, MAXLAYER]
* @param pos int 金字塔中第layer层的第pos([0, layer-1])个元素
* @return int 最大路径和
*
*/
int MaxPathSum(int *pNums, int layer, int pos)
{
    if(MAXLAYER == layer)
    {
        return pNums[Index(layer, pos)];
    }

    /**
     * 第layer层的第pos个元素，只能向第layer+1层的第pos或第pos+1个元素走
     */
    return max(MaxPathSum(pNums, layer + 1, pos + 0), MaxPathSum(pNums, layer + 1, pos + 1))
           + pNums[Index(layer, pos)];
}

int main()
{
    // 数组的大小应该为 MAXLAYER * (MAXLAYER + 1) / 2
    int nums[] = {7, 3, 2, 8, 1, 0, 2, 7, 4, 4, 4, 5, 2 ,6, 5};
    cout << MaxPathSum(nums, 1, 0) << endl;

    return 0;
}

说明：程序测试有限，不足还望指出。请不吝赐教！　　　　　　