算法分析：

具有线性“阶段”划分的动态规划算法。

无论线性dp的状态表示上是一维还是多维的，都是线性上的递推，直白来讲，就是随着一条线进行状态的变化，相比较与背包dp。

DP的阶段沿着各个维度线性增长，从一个或多个边界点开始，有方向地向整个状态空间转移和拓展。

最后每个状态都保留了以自身为“目标“的子问题的最优解

---

主要来看题:

例题：求最长上升子序列

Description

设有由n个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)且b(i)<>b(j) (i<>j)，

若存在i1<i2<i3< … < ie 且有b(i1)<b(i2)< … <b(ie)则称为长度为e的不下降序列。程序要求，当原数列出之后，求出最长的上升序列。

例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。例中13，16，18，19，21，22，63就是一个长度为7的不下降序列，

同时也有7 ，9，16，18，19，21，22，63长度为8的不下降序列。

Input Format

只有一行，为若干正整数（最多1000个数）

Output Format

为两行，第一行为最上升序列的长度。 第二行为该序列

Sample

样例输入

13 7 9 16 38 24 37 18 44 19 21 22 63 15

样例输出

max=8
7 9 16 18 19 21 22 63

分析：最长上升子序列，无非就是在循环过程中判断当前位置的数值与它之前的序列中的数是否能组成上升子序列，长度是否会更长。

最后在dp数组中寻找最大值，此值即为最长上升子序列的长度。至于最长上升子序列，只需记录转移的父亲即可。

例题代码：

#include<bits/stdc++.h>
using namespace std;
int a[1005],n,ans,tend,f[1005],pre[1005];

void pp(int x)//记录转移的父亲，输出此序列
{
	if(!x) return;
	pp(pre[x]);
	cout << a[x] << " ";
}

int main()
{
	while(cin >> a[++n]){}
	n--;//处理输入
	for(int i = 1;i <= n;i++)
    {
		f[i] = 1;//初始化第i个数自己就是一个上升子序列
		for(int j = 1;j < i;j++)//遍历它之前的数
        {
			if(a[i] > a[j])//满足上升关系
        	{
				if(f[i] < f[j] + 1)//长度会更长
         		{
					f[i] = f[j] + 1;//更新
					pre[i] = j;//记录父亲
					if(ans < f[i])
           			{
						tend = i;
						ans = f[i];//更新最长值
					}
				}
			}
		}
	}
	cout <<"max="<< ans <<endl;
	pp(tend);
	return 0;
}

---

例题：挖地雷

Description

在一个地图上有N个地窖（N<=200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的,

也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任一处开始挖地雷，

然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。

Input Format

第一行一个整数n表示有n个地窖 第二行有n个整数表示每个地窖的地雷数 以下有若干行，每行有两个数x,y表示x可以到y，

保证x小于y。 最后一行有两个0，表示输入结束

Output Format

第一行输出挖地雷的顺序。 第二行为最多挖出的地雷数

Sample

样例输入

6
5 10 20 5 4 5
1 2
1 4
2 4
3 4
4 5
4 6
5 6
0 0

样例输出

3-4-5-6
34

分析：先记录路径并存图。求挖出地雷的最多数可以先枚举每一个坑i，寻找与他们相连的坑。如果与它相连的这些坑是从它挖过来的，

并且这样挖的值会比单独挖这个坑的数量更多，那么就更新这个坑（f[j]表示挖到j坑的最大值）f[j]的值并记录f[j]的父亲为i.

最后遍历f数组求最大值，再逐一寻找其父亲并倒序输出即可。

例题代码：

#include <bits/stdc++.h>
using namespace std;

int n,a[205],f[205],fa[205],l[205],ans,num;
stack<int> q;
vector<int> e[205]; 

int main()
{
	ios::sync_with_stdio(false);
//	freopen("file.in", "r", stdin);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	int x = 0, y = 0;
	while (cin >> x >> y)
	{
		if (x == 0 && y == 0) break;
		e[x].push_back(y);
	}
	for (int i = 1; i <= n; i++) f[i] = a[i];
	//时间复杂度：O(n3) 
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < e[i].size(); j++)
		{
			int k = e[i][j];
			if (f[k] < f[i]+a[k]) fa[k] = i;
			f[k] = max(f[k],f[i]+a[k]);
		}
	}
	ans = 0;
	int m = 0;
	for (int i = 1; i <= n; i++)
	{
		if (ans < f[i]) m = i;
		ans = max(ans,f[i]);
	}
	while (m != 0)
	{
		q.push(m);
		m = fa[m];
	}
	while (!q.empty())
	{
		l[++num] = q.top();
		q.pop();
	}
	for (int i = 1; i <= num; i++)
	{
		if (i == num) cout << l[i] << endl;
		else cout << l[i] << '-';
	}
	cout << ans << endl;
	return 0; 
}