DP求最小花费，可以用最短路的思想来做。不过最短路是二维矩阵，这里我们做的是一维。
题意：给你n个点，标号从1 - n，再给出n-1条边，代表从1到2...n之间的距离。三种车票，长度为L1,L2,L3,价格为C1,C2,C3，问你从坐标a到b最少的花费（在坐标点换乘，超出的距离也只能在到达的最近点换乘）。
数据范围：0<L1<L2<L3<10^9,0<C1<C2<C3<10^9，任意两个站之间的距离小于等于L3.n题目没给，开1e4能过。
这就相当于最短路，用f[ ]数组记录，一重for循环 i 从a 开始枚举，到b-1，二重for循环 j 从i+1到b，但是这里有限制条件dis[j] - dis[i] <=L3&&j<=b，可以剪枝。
#include <iostream> #include <stdio.h> #include <string.h> #define LL long long using namespace std; const int maxn=3e4+10; const LL INF=1e18+10; LL dis[maxn],f[maxn]; int l1,l2,l3,c1,c2,c3; LL judge(int j,int i) { LL s=dis[j]-dis[i]; if(s<=l1) return c1; if(s<=l2) return c2; if(s<=l3) return c3; } int main() { int a,b; while(scanf("%d%d%d%d%d%d",&l1,&l2,&l3,&c1,&c2,&c3)!=EOF) { scanf("%d%d",&a,&b); int n; scanf("%d",&n); dis[1]=0; for(int i=2;i<=n;++i) { scanf("%lld",&dis[i]); f[i]=INF; } f[a]=0; for(int i=a;i<b;++i) { for(int j=i+1;j<=b&&dis[j]-dis[i]<=l3;++j) f[j]=min(f[j],f[i]+judge(j,i)); } printf("%lld\n",f[b]); } return 0; }
上面是一种类似背包的求最小花费，下面看二位矩阵的最小花费。
MPC问题
给定一个矩阵cost[][]和其中的一个位置（m，n），写一个函数，返回从到达（0，0）到（M，N）最小成本路径的花费。该矩阵的每个格子代表遍历该格子的花费。到达（M，N）的路径的总成本是该路径上（包括源和目标）所有的费用总和。你只能从开始位置 向右、下和右下走，也就是说，从一个给定的格子（I，J），只有（i+1，j）的（i，j +1）和（i +1， j +1）的可以通过。你可以假设所有的花费都是正整数。
1）最优子结构 的路径到达（M，N）必须通过3格子中的一个：（M-1，N-1）或（m-1，n）或（M，N-1）。到达（M，N），所以最小的花费路径可以写成“3个格子最小的 加[M] [N]的花费”。
minCost(m, n) = min (minCost(m-1, n-1), minCost(m-1, n), minCost(m, n-1)) + cost[m][n]
2）重叠子问题 以下是直接的递归实现的最小花费路径的问题，用的上面的递归函数。MCP问题是具有动态规划必须的两个性质。像其他典型的动态规划（DP）的问题，可通过打表已自下而上的方式避免相同的子问题重复计算。
/ *动态规划实现的MCP问题* / #include<stdio.h> #include<limits.h> #define R 3 #define C 3 int min(int x, int y, int z); int minCost(int cost[R][C], int m, int n) { int i, j; int tc[R][C]; tc[0][0] = cost[0][0]; /* 初始化第一列 cost(tc) array */ for (i = 1; i <= m; i++) tc[i][0] = tc[i-1][0] + cost[i][0]; /* 初始化第一行 */ for (j = 1; j <= n; j++) tc[0][j] = tc[0][j-1] + cost[0][j]; /* Construct rest of the tc array */ for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) tc[i][j] = min(tc[i-1][j-1], tc[i-1][j], tc[i][j-1]) + cost[i][j]; return tc[m][n]; } /* 返回3个整数中最小的 */ int min(int x, int y, int z) { if (x < y) return (x < z)? x : z; else return (y < z)? y : z; } /* 测试 */ int main() { int cost[R][C] = { {1, 2, 3}, {4, 8, 2}, {1, 5, 3} }; printf(" %d ", minCost(cost, 2, 2)); return 0; } 时间复杂度为O（MN）。
