赵天泽

#算法分析：
最多拦截的导弹数很容易理解，就是求最长下降子序列，而要配备的系统数相对难理解一些。这样想：每个系统只能拦截一个下降子序列，一个系统不可能拦截在一个导弹后面而且还更高的另一个导弹，所以每有一个比之前高的导弹就需要多一个系统，也就是上升子序列有多少个数，就需要多少个系统，而要保证全部拦截，所以要求最长上升子序列。这样就明确要求最长上升子序列和最长下降子序列了。

而动态规划的特点在于**将过程中的状态记录并保存下来，这样在每一刻都可以使用所记录下来的之前的状态**。而求最长上升和下降子序列就需要不断在之前的状态上拦截下一个导弹，并和其他子序列比较长度，所以非常合适用动态规划（不好讲清楚，理解不了的话就别理解，去感受，多练.jpg）。
分析这两种方法的区别可以帮助理解动态规划：
1.使用循环从数组a[0]开始，将a[0]作为拦截的第一个导弹
2.使用循环从数组a[0]开始，将a[0]作为拦截的最后一个导弹
如果选用1方法，在计算过程中你会发现，a[0]作为第一个导弹其实包含了将a[1] 作为第一个导弹的情况，只是在a[1]作为第一个导弹的情况下，多加一步判断a[0]是否大于a[1]。同理，计算a[1]时，也会包含a[2]，这样其实和动态规划的思想正好反了过来，反而是2方法，a[1]作为最后一个导弹，包含了a[0]作为最后一个导弹的情况，这才是符合动态规划的方法。

说了这么多，上代码
```c
#include<stdio.h>
int main()
{
	int a[2000];
	int down[10000] = { 0 }, up[10000] = { 0 };//down[i]表示第i+1个数作为最小的数时最长下降子序列的长度。up[i]同理
	int i = 0, j, max_down = 0, max_up = 0;//记录最长下降和上升子序列
	while (scanf_s("%d", &a[i]) != EOF)
		i++;
	int n = i ;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < i; j++)//j要小于i，因为a[i]表示的是子序列最后的数
		{
			if (a[j] > a[i])
			if (down[i] < down[j] + 1)
					down[i] = down[j] + 1;
//将down[i]和加上a[i]这一长度后的down[j]后相比。这一个比较不能少，因为a[j]可以作为很多下降子序列的最后一个数，可能出现down[j]+1还没有down[i]大的情况，这样会导致down[i]减小。
			if (a[j] <= a[i])
				if (up[i] < up[j] + 1)
					up[i] = up[j] + 1;
//同理
		}
		if (down[i] > max_down)
			max_down = down[i];
		if (up[i] > max_up)
			max_up = up[i];
	}
	printf("%d\n%d", max_down + 1, max_up + 1);//因为当初down和up数组都初始化为0，而长度最小应该是1，所以要把这个1加回来。
	return 0;
}
```

最后放一下总是失败的递归代码，只写了求最长下降子序列的方法，没写上升序列的。但在只需要求下降序列的1264题还是无法通过，有没有大佬帮我看一下哪有问题。
#失败的递归算法：
```c
#include<stdio.h>
int max_down = 0;
void t(int* a,int n,int m)//a表示当前的数组，n为当前数组的大小，m表示当前所拦截是第m个导弹
{
	for (int i = 0; i < n; i++)//第一个导弹的循环
	{
		int q = 0;
		int b[20] = { 0 };
		for (int x = i + 1; x <n; x++)
		{
			if (a[x] < a[i] && a[x]>0)
			{
				b[q] = a[x];
				q++;
			}//将所有比当前数组[0]小的数存到新的数组中，用来递归到下一层函数
		}
		if (q == 0)//q==0表示没有比a[0]更低的导弹了
		{
			if (max_down < m)
				max_down = m;//取最大值
		}
		else
		{
			t(b, q,m+1);//b为比a[0]高度小的导弹组成的新数组，q为新数组大小，m+1表示拦截的下一个导弹
		}
	}
}
int main()
{
	int* a[20] = { 0 };
	int i = 0;
	while (scanf_s("%d", &a[i]) != EOF)
		i++;
	t(a, i,1);
	printf("%d", max_down);
	return 0;
}
```

0.0分

2 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

赵天泽

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.2 （C语言描述和c++代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （Java代码）

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

C二级辅导-求偶数和（C语言代码）

简单易懂的C语言动态规划算法（以及分享一下失败的递归算法）

评论区

精彩推荐

C二级辅导-等差数列（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-数字母（C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

模拟计算器（C++代码）

演讲大赛评分（C语言代码）

赵天泽

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.2 （C语言描述和c++代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （Java代码）

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

C二级辅导-求偶数和 （C语言代码）

简单易懂的C语言动态规划算法（以及分享一下失败的递归算法）

评论区

精彩推荐

C二级辅导-等差数列 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-数字母 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

模拟计算器 （C++代码）

演讲大赛评分 （C语言代码）

C二级辅导-求偶数和（C语言代码）

　　评论区

C二级辅导-等差数列（C语言代码）

C语言训练-数字母（C语言代码）

模拟计算器（C++代码）

演讲大赛评分（C语言代码）