二进制枚举与贪心算法

二进制枚举

1.每个元素只有两种状态

2.n很小，时间复杂度是指数级

贪心的两个特性

无后效性-可以这样理解，如果当前的状态可以用于判断下一步的决策，那么就是无后效性，如果当前的状态不足以用于判断后续决策，那就是有后效性，必须要考虑前面的状态。比如打麻将，如果不考虑前面打的牌，按照当前手上的拍出牌，就是无后效性，如果需要考虑前面两步内打了什么牌，那就是有后效性。可以通过把前面两部的状态记录下来，加上现在的状态一起作为当前状态来把有后效性变成无后效性。

最优子结构-一个问题的最优解包含子问题的最优解，这个问题就有最优解

贪心算法的使用又一个技巧，首先假定一个最优解，然后看，贪心解能否替换最优解，如果一定能替换最优解，那么就可以使用贪心算法。在算法第一课，这个时间点有详细讲解。