hdu 2084 数塔 (基础dp)

hdu2084题目链接

题意:dp入门题。。。数字三角形。。

思路:

昨天看mit公开课。。。讲到dp的精髓是sub-problem+ reuse…

为什么自底向上呢。。。

初始化dp[n][i] = a[n][i]其实是在处理只有最后一行的子问题。。。

需要特别强调的是。。处于某个子问题的时候。。。其他部分就好像不存在一样。。。

每一个点只能向下或者向右下两条路可走。。。

那么对于这一点的最大值。。。一定是取后来可走的两点的最大值加上自身。。。

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz