在講述DP算法的時(shí)候，一個(gè)經(jīng)典的例子就是數(shù)塔問(wèn)題，它是這樣描述的：

有如下所示的數(shù)塔，要求從頂層走到底層，若每一步只能走到相鄰的結(jié)點(diǎn)，則經(jīng)過(guò)的結(jié)點(diǎn)的數(shù)字之和最大是多少？
已經(jīng)告訴你了，這是個(gè)DP的題目，你能AC嗎? Input 輸入數(shù)據(jù)首先包括一個(gè)整數(shù)C,表示測(cè)試實(shí)例的個(gè)數(shù)，每個(gè)測(cè)試實(shí)例的第一行是一個(gè)整數(shù)N(1 <= N <= 100)，表示數(shù)塔的高度，接下來(lái)用N行數(shù)字表示數(shù)塔，其中第i行有個(gè)i個(gè)整數(shù)，且所有的整數(shù)均在區(qū)間[0,99]內(nèi)。 Output 對(duì)于每個(gè)測(cè)試實(shí)例，輸出可能得到的最大和，每個(gè)實(shí)例的輸出占一行。 Sample Input 1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Sample Output 30 //我這里只考慮了一組數(shù)據(jù),需要測(cè)試多組數(shù)據(jù)請(qǐng)自行更改
#include<bits/stdc++.h> #define ll long long using namespace std; const ll maxn=101; ll a[maxn][maxn]; int main() {ll n;//n:幾層的塔cin>>n;for(ll i=1;i<=n;i++)for(ll j=1;j<=i;j++)scanf("%lld",&a[i][j]);//向數(shù)塔輸入數(shù)字// 如果從上往下看,這個(gè)問(wèn)題就變得很復(fù)雜 // 但是如果自底向上遞推就能解決問(wèn)題 // // 任何一個(gè)格子向下走的時(shí)候都有兩種方案,不知道選哪個(gè)可以獲得全局最優(yōu)解 // 那么對(duì)于每?jī)蓚€(gè)相鄰的格子,找出他們兩最大的值,然后賦值給他們上面的那個(gè)格子 // 1 // 3 4 // 1 3 7 // 1 6 4 5 // 5 7 6 7 4 // 對(duì)于左下角的5,7=>1 // 5和7中7最大,那么1+7=8 // 就是說(shuō)從元素較多的底下往上推,不用管選擇哪個(gè)的問(wèn)題 // 每一次最好的結(jié)果都篩選出來(lái)了for(ll i=n;i>=2;i--)//把i這行最好的賦給i-1,所以i要大于2而不是大于1for(ll j=1;j<=i-1;j++)//枚舉i這行每?jī)蓚€(gè)相鄰配對(duì),所以j<=i-1而不是j<=i {a[i-1][j]+=max(a[i][j],a[i][j+1]);}cout<<a[1][1]<<endl; // a[1][1]收集了a[2][1]和a[2][2]中最大一個(gè) // 而a[2][1]又收集了a[3][1]和a[3][2]中最大一個(gè)...... }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zyacmer/p/9905606.html

總結(jié)

以上是生活随笔為你收集整理的数塔(hdoj 2084,动态规划递推)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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