歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

數字三角形(遞歸、動態規劃)

題目描述:
計算出從三角形的頂至底的一條路徑,使該路徑經過的數字總和最大(每個數字可以選擇往左下或者右下方向,例如下圖中的“3”可以選擇數字“8”或者“1”,但是不可以選擇數字“0”和數字“9”)。
7
3 9 ①
8 1 0 ② ③
2 7 4 4 ④ ⑤ ⑥
4 5 2 6 5 ⑦ ⑧ ⑨ ⑩

注意:
1、不是選擇每層中數值最大的那個。
2、不是在符合要求的路徑中,選擇數值最大的那個。
3、上面2個說法是有區別的。
PS:
初看這個題目,也許會理解成注意事項中的第一點,仔細思考這個錯誤的理解,
換個說法,其實是錯誤的理解成注意事項中的第二點。合理的利用這2個錯誤,可以實現下面的算法。

算法:
假如這個三角形就只有1個數字,結果:①
假如這個三角形就只有3個數字,結果:①+max(②,③)
假如這個三角形就只有6個數字,結果:max(max(①+②+④,①+②+⑤),max(①+③+⑤,①+③+⑥))
代碼實現:

 #include <iostream>
#include <cstring>
#include <stdio.h>
#define MAX 100+1
#define Route "/home/wahaha/桌面/123"
using namespace std;
int num[MAX][MAX],n;//n代表層數 h代表行數 l代表列數
int way(int h, int l)
{
    return h == n ? num[h][l]:num[h][l]+max(way(h+1,l),way(h+1,l+1));
}
int main(void)
{
    memset(num,0,sizeof(num));
    freopen(Route,"r",stdin);
    while(cin>>n)
    {
        for(int h=1; h<=n; h++)
          for(int l=1; l<=h; l++)
              cin>>num[h][l];
        cout<< way(1,1) <<endl;
    }
    return 0;
}

Copyright © Linux教程網 All Rights Reserved