文档介绍：Pascal动态规划
[题2] 数塔
如下图所示的数塔，从顶部出发，在每一结点可以选择向左下走或是向右下走，一直走到底层，要求找出一条路径，使路径上的数的和最大。数塔层数用n表示，1<=n<=100。
[题2] 数塔
Pascal动态规划
[题2] 数塔
如下图所示的数塔，从顶部出发，在每一结点可以选择向左下走或是向右下走，一直走到底层，要求找出一条路径，使路径上的数的和最大。数塔层数用n表示，1<=n<=100。
[题2] 数塔
贪心法。时间上有保证，但得不到最优解。主要原因是贪心法只顾眼前利益，不考虑长远利益。
在规定时间内得到正确结果，唯一的方法就是“动态规划”。
下面以示意图表示动态规划的过程：所选路径为：9-12-10-18-10
注意分析时，有以下几个特点：
（1）将问题划分成了4个阶段；
（2）每个阶段均得到了“部分”的最优解，得到最优解时，需要进行条件判断；
（3）从最下面一层往顶层推导。
[题3] 棋盘路径问题
【题目简介】
有一个n*m的棋盘，左下角为（1,1），右上角为（n,m），如下图： 
有一颗棋子，初始位置在（1,1），该棋子只能向右走或者向上走，问该棋子从（1,1）到（n,m）一共有几条路径？
输入：两个整数n和m
输出：一个数，路径总数
[题3] 棋盘路径问题
【题目简介】
如果使用枚举的方法，必定有很多路径被重复走过，这样，势必造成程序运行时间的浪费，当n和m的值比较大的时候，程序很可能超时。为了避免程序的重复运行，我们可以通过记录点（1,1）到任意一个点（I,j）的路径总数来解决这个问题。假设F[I,j]是点(1,1)到点(I,j)(1≤i≤n, 1≤j≤m)的路径总数，因为棋子在棋盘中只能向右或者向上走，所以棋盘中只能2个点的棋子可以走到点（I,j），即点(I,j-1)和(i-1,j)，这样，我们就可以知道，F[I,j]必定是F[I,j-1]和F[i-1,j]的和，即
F[i,j]=F[i-1,j]+F[i,j-1]
【例4】街道问题
在下图中找出从左下角到右上角的最短路径，每步只能向右方或上方走。
【例4】街道问题
在一般情况下，如果我们用二维数组H(i，j)和V(i，j)分别表示水平方向和竖直方向的各路段长度，如H(1，2)表示水平方向上路口 (1，1)到路口(1，2)的路段长度，V(1，2)表示竖值方向上路口(0，2)到路口(1，2)的路段长度，则有公式：如
dpl(i，j)=min{dpl(i-1，j)+v(i，j)，dpl(i，j-1)+h(i，j)}
[题5] 机器分配
【问题描述】
总公司拥有高效生产设备M台，准备分给下属的N个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M≤15，N≤10。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。保存数据的文件名从键盘输入。
数据文件格式为：第一行保存两个数，第一个数是设备台数M，第二个数是分公司数N。接下来是一个M*N的矩阵，表明了第I个公司分配J台机器的盈利。
[题5] 机器分配
【分析】
这是一个典型的动态规划试题。用机器数来做状态，数组F[I，J]表示前I个公司分配J台机器的最大盈利。则状态转移方程为
F[i，j]=Max{F[i-1，k] + Value[i，j-k]}
（0〈=K〈=J〉
[题6] 0-1背包问题
【题目】
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
[题6] 0-1背包问题
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
[题7] 完全背包问题
【题目】
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
[题7] 完全背包问题
【基本思路】
这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，令f[i][v]表示前i种物品恰