數字金字塔最大路徑和——遞歸

題目描述

假設有如下所示的一個數字金字塔，現在，要求寫一個程式來查找從頂點到底部任意處結束的路徑，使路徑經過的數字的和最大，并輸出該路徑的最大和。比如以下金字塔的和最大路徑的和為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 ;  // 金字塔的最大層數 int  Index( int  layer,  int  pos) {      return  layer * (layer -  1 ) /  2  + pos; } int  MaxPathSum( int  *pNums,  int  layer,  int  pos) {      if (MAXLAYER == layer)     {          return  pNums[Index(layer, pos)];     }      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 ; }

  說明：程式測試有限，不足還望指出。請不吝賜教！　　　　　　

轉載于:https://www.cnblogs.com/fengkang1008/p/4794855.html