一道关于pascal的问题

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。

例题：
给你一个数字三角形, 形式如下:
1
2 3
4 5 6
7 8 9 10
找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.
无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)}
对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么简单了。
解决方法：
我们尝试从正面的思路去分析问题，如上例，不难得出一个非常简单的递归过程 :
f1:=f(i-1,j+1); f2:=f(i-1,j);
if f1>f2 then f:=f1+a[i,j] else f:=f2+a[i,j];
显而易见，这个算法就是最简单的搜索算法。时间复杂度为2n，明显是会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。为了避免浪费，很显然，我们存放一个opt数组：Opt[i, j] - 每产生一个f(i, j)，将f(i, j)的值放入opt中，以后再次调用到f(i, j)的时候，直接从opt[i, j]来取就可以了。于是动态规划的状态转移方程被直观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而