分析：
此题和数塔问题很类似，可以划分为一个多阶段决策的问题来解决。按照动态规划自顶向下分析，自底向上计算的思路。
设w[i,j]表示该位置到A点的最短路径，LX[i,j]表示点（i-1,j）到点(i,j)垂直方向上的距离，LY[i,j]表示点（i,j-1）到点(i,j)水平方向上的距离，则不难推出方程： w[i,j]=min((w[i-1,j]+LX[i,j]),w[i,j-1]+LY[i,j]) w[0,0]=0 //递归或递推边界
例五：0/1背包问题 问题描述：
有 n 件物品x1, x2, …, xn , 每件物品有一个价值和一个重量，分别记为： v1,v2, …vn w1,w2, …wn
其中所有的 wi 均为整数。 现有一个背包，其最大载重量为m，要求从这n件物品中任取若干件（这些物品每样只有一件，要么被装入要么被留下）。问背包中装入哪些物品可使得所装物品的价值和最大？ （我们只需要求出最大价值，不需要求出具体拿的是哪些物品） 例如，m=23, n = 5, vi : 19 24 33 45 50 wi : 5 6 8 11 12 最大价值为：95
分析：
如果想用贪心，先求出平均价值，然后从高到低的方法来取，如果有一个背包的容量为10，共有3个物品，体积分别是3、3、5，价值分别是6、6、9，那么你的方法取到的是前两个物品，总价值是12，但明显最大值是后两个物品组成的15。因此贪心的方法不能得到正确结果。
换一个更简单的方式来思考：每个物品只有2种选择，要么放入，要么不放入。 （1）放入：问题转换为在背包载重为m-wi的情况下，在其它n-1件物品中挑选，求得价值和最大。等把这个子问题求出后，再加上vi的价值就是整个问题的最优解了。 （2） 没放入：那么就当xi 根本不存在，直接解物品数量为n-1，背包载重为m的子问题。子问题的最优解就是问题的最优解。
定义函数f(i,j)为在1~i 件物品中选若干件装入限重为 j 的背包中的最大价值和， 那么根据上面关于第 i 件物品是否装入了背包的情况分析，我们得出关系式：
(1)当第I件物品要装入背包时，f(i,j) := (i-1件物品，限重为j-w[i]的最优解)+ v[i], 即： f(i,j) := f(i-1, j-w[i]) + v[i]
当然，第i件物品要装入是有条件限制的：第i 件物品重量小于等于背包限重，即 w[i] <= j
（2）当第i件物品不装入背包时，f(i,j) :=i-1件物品，限重为m的最优解，即： f(i,j) := f(i-1, j)
求得装入或者不装入第 i 件物品的限重为J的背包的最大价值，只需要比较这两种情况下谁的价值更大，更大者为当前问题的最优解。
f(i,j)=max{ f(i-1, j-w[i]) + v[i] , f(i-1, j) } 该方程递归结束的边界条件是：当j=0时，f(i,0)=0。
在按自底向上的动态规划方式求解问题时，其实主要就是做一件事：
按问题规模从小到大地求解问题，把每阶段求得的问题的最优解保存在表格（数组）中，以便在下一阶段求解更大的问题时，可以直接查表引用子问题的最优解。 （类似于递推）
阶段的分析：
将n件物品放入背包，故可以把阶段划分为n个。把在前I件物品中选取物品放入背包作为第I个阶段。 状态的分析：
在第i 个阶段有多少个状态呢?因为包的容量为m，故在每个i 阶段都有m个状态：f(i,1)、f(i,2)、f(i,3)……f(i,m-1)、f(i,m)。
而这m个问题的求解基础是第I-1个阶段的m个子问题。这些子问题的最优解已经先于此时求得，保存在f[I-1,1], f[I-1,2], …, f[I-1,m]中，现在只需要直接引用它们的值就可以了。这就是动态规划自底向上的体现。
之所以能求得之前的状态，是因为有一个边界：f(i,0)=0。 决策的分析：
只有两个，在前I件物品中，限重为J的条件下，装入第I件物品还是不装入第I件物品。比较这两种情况的价值和，谁大谁就是最优解。
优化空间复杂度
以上方法的时间和空间复杂度均为O(VN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下：
for i=1..N for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
例六：采药（noip2006普及） 例七：完全背包问题
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本思路
这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v} O(VN)的算法
这个算法使用一维数组，先看伪代码：
for i=1..N for v=0..V
f[v]=max{f[v],f[v-cost]+weight}
这个伪代码与01背包的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢？首先想想为什么01中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果
f[i][v-c[i]]，所以就可以并且必须采用v=0..V的顺序循环。这就是这个简单的程序为何成立的道理。
例八：usaco 3.1总分
例九：usaco3.4.4