HDOJ2084数塔问题

数塔问题

题目要求从顶层走究竟层。若每一步仅仅能走到相邻的结点，求经过的结点的数字之和最大值。

非常经典的DP，能够这样考虑，要求从塔顶到塔底最大路径之和。计算时能够考虑自底向上，走最后一步所选的数一定是塔底的某个值。向上退一层，对于倒数第二步。所走的是塔底往上一层较大的那个数，此时能够将倒数第二步所走的数与塔底较大的值加起来，记忆存储，依次往上推。一直推到塔顶。此时所计算出的结果一定是最大的。

以下这张图非常清晰地反映出了解题的思想。

此时能够用方程表示为

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

AC代码例如以下：