天威难测

用户名：uq_61498387617

访问量：1331

签　名：

岁月在你我呼吸间流浪

等　　级
排　　名	8308
经　　验	1240
参赛次数	1
文章发表	10
年　　龄	0
在职情况	学生
学　　校	南京中医药大学
专　　业	中药学类

　　自我简介：

TA的其他文章

[python]动态规划&遍历
浏览：154

动态规划思考全过程
浏览：197

动态规划与优化后的动态规划哈哈哈哈
浏览：676

你可能喜欢

动态规划思考全过程

　　作者: 天威难测　　　　发表时间：2022-02-23 09:59:29 浏览：197　|　评论：0　

原题链接：蓝桥杯算法训练VIP-拦截导弹

# 题目描述
![在这里插入图片描述](https://img-blog.csdnimg.cn/75173d5284c9433d87276d1d894e2e48.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5aSp5aiB6Zq-5rWL,size_20,color_FFFFFF,t_70,g_se,x_16)

# 思路
最初我想把整体高度逆序排布为 Height[ n ] ，然后利用动态规划

创建一个列表 dp[ i ]，意思是第 i 个导弹之前比它低的导弹数量

所以状态转移方程：

```python
dp[ i ] = max{dp[ j ] + 1, 1}(0 <= j < i)
```

最开始代码如下：

```python
Height = input().split()
H = [0 for _ in range(len(Height) + 1)]
dp = [0 for _ in range(len(Height) + 1)]
for i in range(len(Height)):
    H[-(i + 1)] = int(Height[i])
print(H)
for i in range(1, len(Height)):
    if(H[i] > H[i - 1]):
        dp[i] = dp[i - 1] + 1
    else:
        dp[i] = dp[i - 1]
print(dp)

```
运行结果如下：
![在这里插入图片描述](https://img-blog.csdnimg.cn/3490f643bed94f27ba7b1090df9d566f.png)
我发现问题出现在它一定是以第一个为初始拦截目标，并且判断大于小于关系的时候没有一个“可跳跃”的联系，因此我准备再添加一个 for 循环，让它获得联系

```python
Height = input().split()
H = [0 for _ in range(len(Height))]
dp = [1 for _ in range(len(Height))]
for i in range(len(Height)):
    H[-(i + 1)] = int(Height[i])
print(H)
for i in range(1, len(Height)):
    for j in range(i):
        if(H[j] < H[i] and dp[i] < dp[j] + 1):
            dp[i] = dp[j] + 1
print(max(dp))

```
在这边可以获得最多拦截导弹个数，再经过思考，在之前，比如说“高僧斗法”那种题目里面，我一直定向思维，要从小到大的顺序，在循环方面，利用 max() 函数来进行返回值限定，但是在这边我后来改掉了逆向函数，发现其实效果是以昂的，不是说一定要利用原来的那种方法：

```python
Height = input().split()
dp = [1 for _ in range(len(Height))]
for i in range(len(Height)):
    Height[i] = int(Height[i])
for i in range(1, len(Height)):
    for j in range(i):
        if(Height[j] > Height[i] and dp[i] < dp[j] + 1):
            dp[i] = dp[j] + 1
print(max(dp))
```

# 最终源码

```python
Height = input().split()
dp_1 = [1 for _ in range(len(Height))]
dp_2 = [1 for _ in range(len(Height))]
for i in range(len(Height)):
    Height[i] = int(Height[i])

for i in range(1, len(Height)):
    for j in range(i):
        if(Height[j] > Height[i] and dp_1[i] < dp_1[j] + 1):
            dp_1[i] = dp_1[j] + 1
        if(Height[j] < Height[i] and dp_2[i] < dp_2[j] + 1):
            dp_2[i] = dp_2[j] + 1

print(max(dp_1))
print(max(dp_2))

```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

天威难测

TA的其他文章

你可能喜欢

台球碰撞（C语言代码）

回文数字（C++代码）

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

数列排序（C语言代码）

【绝对值排序】（C语言代码）

动态规划思考全过程

评论区

精彩推荐

【计算两点间的距离】（C语言代码）

兰顿蚂蚁（C++代码）

妹子杀手的故事（C语言代码）

C二级辅导-阶乘数列（C语言代码）

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

【计算两点间的距离】（C语言代码）

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

Hello, world! （C语言代码）

关于float，double变量的几点说明

图形输出（C语言代码）

天威难测

TA的其他文章

你可能喜欢

台球碰撞 （C语言代码）

回文数字 （C++代码）

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

数列排序 （C语言代码）

【绝对值排序】 （C语言代码）

动态规划思考全过程

评论区

精彩推荐

【计算两点间的距离】 （C语言代码）

兰顿蚂蚁 （C++代码）

妹子杀手的故事 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

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

【计算两点间的距离】 （C语言代码）

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

Hello, world! （C语言代码）

关于float，double变量的几点说明

图形输出 （C语言代码）

台球碰撞（C语言代码）

回文数字（C++代码）

数列排序（C语言代码）

【绝对值排序】（C语言代码）

　　评论区

【计算两点间的距离】（C语言代码）

兰顿蚂蚁（C++代码）

妹子杀手的故事（C语言代码）

C二级辅导-阶乘数列（C语言代码）

【计算两点间的距离】（C语言代码）

图形输出（C语言代码）