Hdu/Hdoj 2048 数塔

2009-04-29 15:48:24

Accepted

2084

15MS

300K

440 B

C++

Master Jedi

对于问题“从第i层第j个结点出发 如何向下走到底层 使所经过的权值最大”，有2个选择：走左边 和 走右边。
做出1个选择：假设选择走左边结点k，然后再按一定路线（不必考虑具体路线，假设已知）走到底层，可以得到最优解。
那么随之发生的子问题是：“从左结点k出发 如何向下走到底层 使所经过的权值最大”。
用反证法容易证明：从第i层第j个结点出发 向下走到底层的最优路线，包含了从左结点k出发向下走到底层的最优路线。该问题具有最优子结构性质。
而子问题“从第i层第j个结点出发 如何向下走到底层 使所经过的权值最大”很明显具有重叠性。
于是自底向上DP即可解决问题。
f[i][j]：表示从第i层第j个结点出发向下走到底层能够得到的最大权值。
状态转移方程：f[i][j]=MAX(f[i+1][j],f[i+1][j+1]);