共计 563 个字符，预计需要花费 2 分钟才能阅读完成。
问题描述：
某国为了防御敌国的导弹袭击，发展中一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于等于前一发的高度。某天，雷达捕捉到敌国导弹来袭。由于该系统还在试用阶段，所以只用一套系统，因此有可能不能拦截所有的导弹。
输入：
导弹依次飞来的高度 [h1, h2, h3,…hn]
输出：
最多能拦截的导弹数目
思路：
导弹飞来，我们可以选择拦截或者不拦截，但拦截第一次后，后面的拦截高度受限。一次拦截结果是成功 / 失败，我们需要将拦截成功次数 score 最大化。
1 拆分子问题
一次拦截结果是成功或者失败，score 可加 1 或保持不变。对第 i 个导弹，拦截它的次序可能是第 1 次，第 2 次。。。第 i 次，所以我们需要计算的是第 1 次，第 2 次。。。第 i 次拦截的成功次数
2 得分计算
第 i 次拦截的成功次数为 S(i) = max(S(j)+shootScore(i,j+1))，其中,1<=j<i，shootScore(i,j+1)表示当第 i 个导弹飞来，我们已经进行了 j 次拦截，第 j + 1 次拦截的成功 / 失败，成功为 1，失败为 0，初始值 S(1)=1
3 时间复杂度
拆分出的子问题个数是 n，第 i 个子问题需要考虑 i - 1 种情况，计算 shootScore(i,j+1)需要进行 i -j- 1 次计算，所以时间复杂度为 O(n3)
4 代码
正文完
发表至： javascript
2019-08-16
