程序思想介绍之动态规划【代绿色草原发】

凯撒

学了这么久的信息学，来给大家介绍下一些很有趣的思想吧……
  动态规划是一个比较经典的思想，其实他的本质和递推是一样的（大家应该知道递推哈，比如经典的斐波纳契数列，递推式为F1=1,F2=1,Fn=Fn-1+Fn-2.这个就是递推）。不过显然从名字就知道这种递推是动态的。动态规划和递推也有着类似之处，但是他的边界的设定一定要非常准确（哎，话说好多题我就栽在边界上了……）。而且很多动态规划的题目的边界都不是很显然的……
  下面来看一个经典的题以详细的介绍这种思想。


问题
  给出一个数塔（数塔就是全部由数字做成的塔……），第i行有i个数，从顶部开始走，每次向左走或是向右走，设计程序找出一条路径，使得路径上的值之和最大。只要求输出最大值。
  比如给出的数塔是这样子的：
       2
     3   5
  3   7   9
那你的程序就应该输出16（选择的路径是2——5——9，加起来是所有路径中值最大的，为16）。
  

呃，当然，这个肯定不能手工算，要是别人给出一个n^n^n^n^………………那么大的数塔后果可就…………
那么，有没有什么好的方法可以用计算机来完成这个工作呢？当然有啦…………
下面：
   预知后事如何，且听下回分解。

凯撒

可怜的草原，什么时候你的网速能好起来呢？

绿色草原

哎，凯撒啊，话说你把数塔的版排错了……