有一个由非负整数组成的三角形, 第一行只有一个数，除了最下行之外，每个数的左下方和右下方各有一个数。从第一行的数开始, 每次可以往左下或右下走一格, 直到走到最下行,把沿途经过的数全部加起来. 如何走才能使得这个和尽量大?
位置看成是状态，设状态有指标函数 d 表示从该位置出发能够得到的最大和
可以看出子结构：对于每个节点状态，选择能够到达该状态的最大的那个 d 与自身相加是最优的。如果还不是最优，那么后续可以沿用这个状态得到全局更优的结果，说明满足最优子结构性质。
故推出：
2分钟阅读
有一个由非负整数组成的三角形, 第一行只有一个数，除了最下行之外，每个数的左下方和右下方各有一个数。从第一行的数开始, 每次可以往左下或右下走一格, 直到走到最下行,把沿途经过的数全部加起来. 如何走才能使得这个和尽量大?
位置看成是状态，设状态有指标函数 d 表示从该位置出发能够得到的最大和
可以看出子结构：对于每个节点状态，选择能够到达该状态的最大的那个 d 与自身相加是最优的。如果还不是最优，那么后续可以沿用这个状态得到全局更优的结果，说明满足最优子结构性质。
故推出：
di,j=ai,j+max{di+1,j+1,di,j+1}