/*

數(shù)塔問題：

9

12 15

10 6 8

2 18 9 5

19 7 10 4 16

有形如圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，

一直走到底層，要求找出一條路徑，使路徑上的值最大。

這道題如果用枚舉法，在數(shù)塔層數(shù)稍大的情況下(如40)，則需要列舉出的路徑條數(shù)將是一個(gè)非常龐大的數(shù)目。

如果用貪心法又往往得不到最優(yōu)解。

在用動(dòng)態(tài)規(guī)劃考慮數(shù)塔問題時(shí)可以自頂向下的分析，自底向上的計(jì)算。

從頂點(diǎn)出發(fā)時(shí)到底向左走還是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到最大值，

只要左右兩道路徑上的最大值求出來了才能作出決策。

同樣的道理下一層的走向又要取決于再下一層上的最大值是否已經(jīng)求出才能決策。

這樣一層一層推下去，直到倒數(shù)第二層時(shí)就非常明了。

如數(shù)字2，只要選擇它下面較大值的結(jié)點(diǎn)19前進(jìn)就可以了。

所以實(shí)際求解時(shí)，可從底層開始，層層遞進(jìn)，最后得到最大值。

總結(jié)：此題是最為基礎(chǔ)的動(dòng)態(tài)規(guī)劃題目，階段、狀態(tài)的劃分一目了然。

而決策的記錄，充分體現(xiàn)了動(dòng)態(tài)規(guī)劃即“記憶化搜索”的本質(zhì)。

*/

#include [i]

#define MAX 20

using namespace std;

int main()

{

cout > n;

int a[MAX+1][MAX+1][3];? ? ? ? //[0]用來存數(shù)，[1]參與運(yùn)算，[2]表示向左(0)，還是向右(1)

//輸入數(shù)塔

for(int i = 1; i > a[i][j][0];

a[i][j][1] = a[i][j][0];

a[i][j][2] = 0;

}

}

cout = 1; --i)? ? ? ? //從倒數(shù)第二行開始

{

for(int j=1; j??a[i+1][j+1][1])? ? ? ? //左邊大

{

a[i][j][2] = 0;? ? ? ? ? ? ? ? //選擇左邊

a[i][j][1] += a[i+1][j][1];

}

else? ? ? ? //右邊大

{

a[i][j][2] = 1;? ? ? ? ? ? ? ? //選擇右邊

a[i][j][1] += a[i+1][j+1][1];

}

}

}

//輸出數(shù)塔

for(int i = 1; i??";

j += a[i][j][2];

}

cout

總結(jié)

以上是生活随笔為你收集整理的python 动态规划 数塔_数塔问题，简单的动态规划算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。