算法——找规律

本质

这类题型的本质就是发现规律从而找到更简单的算法

例题

• 暴力解法那就是从前往后或者从后往前枚举所有可能的情况，算法复杂度较高。
• 首先要结合正难则反的思路，然后把s->t的最小操作次数转换成t->s的最小操作次数（当然*2和-1要换成/2和+1），我们可以分情况讨论，t的上一个数变成t有如下几种情况：
  
  可以发现，如果t是奇数t的上一个数就是t+1；如果t是偶数的话，t的上一个数可以是t+1也可以是t/2，不过，加x个1再除以2等价于个除以2再加y个1而，y<x，因此偶数的第三种情况的操作次数一定大于前两种情况，所以如果t是偶数的话就除以2。
  不过后来发现以上假设都是基于t > s的情况，如果t < s 有些推论就不成立，比如偶数中的第三种类型最前面不一定有*2。故此，我们补充完整的情况：
  

• 少量的箭引爆气球就是尽量在重叠区射箭，一次性引爆多个气球。对于没有和其他气球重叠起来的气球，需要单独的箭来引爆。这里有一个问题，就是假设一个气球分别和两个气球重叠，应该向那个区域射箭？其实无论向哪儿射箭，最后没被射的气球都成了单独的气球，仍旧需要箭射爆。所以只要是重叠区以及单独的气球都需要射箭。
• 我们要找的就是重叠区和单独气球的数量。