HDOJ2084數塔問題

數塔問題

題目要求從頂層走究竟層。若每一步僅僅能走到相鄰的結點，求經過的結點的數字之和最大值。

非常經典的DP，能夠這樣考慮，要求從塔頂到塔底最大路徑之和。計算時能夠考慮自底向上，走最後一步所選的數一定是塔底的某個值。向上退一層，對于倒數第二步。所走的是塔底往上一層較大的那個數，此時能夠将倒數第二步所走的數與塔底較大的值加起來，記憶存儲，依次往上推。一直推到塔頂。此時所計算出的結果一定是最大的。

以下這張圖非常清晰地反映出了解題的思想。

此時能夠用方程表示為

Dp[i][j]+=max{dp[i-1][j],dp[i-1][j-1]}

AC代碼例如以下：