当前位置: 代码迷 >> 综合 >> HDOJ-2084 数塔(简单DP)
  详细解决方案

HDOJ-2084 数塔(简单DP)

热度:34   发布时间:2023-12-09 20:48:43.0

题目:HDOJ-2084

题意:
有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过
的结点的数字之和最大是多少?
在这里插入图片描述
每个测试实例的第一行是一个整数N(1 <= N <= 100),表示数塔的高度,接下来用N行数字表示数塔,其中第i行有个i个整数。

思路:
用到递推的思想。
对于上图的2,19和7中选较大的19,加到2中;对于18,7和10中选较大的10,加到18中,以此类推…
得到状态转移方程:
DP[ i ][ j ] += max (DP[ i+1 ][ j ] , DP[ i+1 ][ j+1 ])

以下代码:

#include<cstdio>
#include