共计 1179 个字符,预计需要花费 3 分钟才能阅读完成。
HDU 2048 数塔
问题描述:
题目链接 - 点我查看题目
给出一个数塔,要求从顶层走到底层,每一步只能从高层走到相邻的低层节点,求经过的结点的数字之和最大是多少?
动态规划的定义
dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.
动态规划是通过拆分问题,定义问题状态和状态之间的关系,使得问题得以递推(或者说分治)的方式去解决。
对于动态规划,可能会产生一些误解,将重点放在如何递推的求解问题,但 如何拆分问题 ,才是动态规划的核心。而拆分问题,靠的就是 状态的定义 和状态转移方程的定义。
1、状态的定义
首先,我们假设使用一个二维数组 dp 来表示这个数塔,类似这样:
7 0 0 0 0
3 8 0 0 0
8 1 0 0 0
2 7 4 4 0
4 5 2 6 5
数组中数塔之外的地方我们将数值填充为 0,其中 dp0 表示数塔最顶部,dp1 和 dp1 分别表示 dp0 下一层的左右两个相邻结点。
状态定义之前,我们首先需要进行 问题的定义 和子问题的定义
有人可能会问了,题目都已经在这了,我们还需定义这个问题吗?需要,原因就是这个问题在字面上看,找不出子问题,而没有子问题,这个题目就没办法解决。
所以我们来重新定义这个问题:
- 给定一个 $I * J$ 大小的二维数组 $dp$
- 设 $F_{i,j} (i<I,j<J)$ 为 $dp[i][j]$ 结点到达底部所经过结点的最大数字之和
- 求 $F_{0,0}$ 的值为多少
如此,以上的 $F{i,j}$ 就是我们所说的 状态 ,定义中的“$F_{i,j}$ 为 $dp[i][j]$ 结点到达底部所经过结点的最大数字之和“就是我们所说的 状态的定义 。
对于 $F_{i,j}$ 来讲,$F_{i-1,j}$ 和 $F_{i-1,j+1}$ 就是 $F_{i,j}$ 的子问题:因为 $dp[i][j]$ 结点往下一层结点走的时候只有这两个相邻的结点可以选择
2、状态转移方程
上述状态定义好之后,状态和状态之间的关系式,就叫做 状态转移方程 。
在上一步我们得到了状态的定义:
$F_{i,j}$ 为 $dp[i][j]$ 结点到达底部所经过结点的最大数字之和
则状态转移方程为:
$F_{i,j}$ = $dp[i][j]$ + $max(F_{i-1,j},F_{i-1,j+1})$
用语言解释一下就是:往下一层走的时候,选择两个结点中状态值最大的那一个
因为最底层的状态值就是本身的值,所以,我们就可以通过该方程从最底层一直往上递推,求得最高层的解
这里可以看出,状态转移方程就是定义了问题与子问题之间的关系,也可以看出,状态转移方程就是一个带有条件判断的递推式。
总的来说,动态规划是一种解决问题的观察角度,让问题能够以递推的方式来解决。所以,如何分析问题,才是动态规划的重点
最后,附上我之前的解题报告:解题报告链接 - 点我查看解题报告