动态规划之导弹拦截

首先做一下求递增子序列问题

采用动态规划策略设计实现算法，找出由n个数组成的序列的最长单调递增子序列。

联想kmp算法进行字符串匹配时，引入一个辅助数组next数组（突然想到的，日后发觉不对再补，该睡觉了）
我们这里也引入一个辅助数组d数组
状态为当前的最长递增子序列，用d[i]数组记录a数组前i+1个数里可以形成递增序列的下标
d[i]=d[{a数组前i个数里小于a[i]的的d[j]的最大值的下标}]+1
输入输出如下：

代码为

#include<iostream>
#define min -100
using namespace std;
int a[100],d[100],b[100];//a数组为输入数组，d数组存放a[i]在递增子序列的序号，b数组为最后形成的递增子序列
void main()
{
	int n,i,j,m,mm;
	cin>>n;	
	for(i=0;i<n;i++)
		cin>>a[i];
	d[0]=1;
	for(i=1;i<n;i++)
	{
		m=min;//m为a数组前i个元素里，比a[i]小的d[j]最大值，mm存放最大值的下标
		for(j=0;j<i;j++)//筛选a数组前i个数里小于a[i]的d[j]最大值
			if(a[j]<a[i]&&d[j]>m)
			{
				m=d[j];
				mm=j;
			}
		if(m==min)//数组a的前i个数都大于
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20