Python（贪心算法）问题 H: 导d拦截

问题 H: 导d拦截

题目描述

某国为了防御敌国的导d袭击，开发出一种导d拦截系统，
但是这种拦截系统有一个缺陷：
虽然它的第一发炮d能够到达任意的高度，但是以后每一发炮d都不能高于前一发的高度。
某天，雷达捕捉到敌国的导d来袭，由于该系统还在试用阶段。
所以一套系统有可能不能拦截所有的导d。

输入导d依次飞来的高度（雷达给出的高度不大于30000的正整数）。
计算要拦截所有导d最小需要配备多少套这种导d拦截系统。

输入

n颗依次飞来的高度（1≤n≤1000）

输出

要拦截所有导d最小配备的系统数k

样例输入

389  207  155  300  299  170  158  65

样例输出

2

解答（贪心算法）：

while True:
    try:
        s = list(map(int, input().split()))
        dp = [1 for i in range(len(s))]
        # 根据for循环的循环次数创建元素全为1的列表
        # 例如循环了8次则dp=[1, 1, 1, 1, 1, 1, 1, 1]
        for i in range(len(s)):
            for j in range(i):
                if s[j] < s[i]:  # s[i] 是当前的数字,j是动态的
                    dp[i] = max(dp[i], dp[j] + 1)
                    # 如果符合条件就在相应的i处实现元素值的增加
                    # 最终会出现一个增序数位置的数字递增效果
        print(max(dp))
    except:
        break

答案不唯一，必定有更加优化的解法欢迎分享