1.贪心和枚举
1.1贪心
贪心指每一步都做出当前最优的选择。一般解决的问题有如下特点：局部最优能导致全局最优。
典型的贪心问题：
1. 纸币面额有1元、2元、10元、100元。问凑出正好x元最少要多少张纸币。
【思路】
显然是尽量取面额大的，因为有整除关系，多张面额小的一定可以被一张面额大的代替。
（如果没有整除关系怎么办？）
2. 纸币面额有a[1]元，a[2]元......a[n]元。问至少凑出x元最少需要多少张纸币？（或者问，x张纸币最多可以凑多少元）
【思路】
显然的贪心算法。每次尽量取面额大的即可。
1. 2枚举
1.2.1朴素枚举
传统的for循环（嵌套）。一般考察知识点的题目用枚举也可以获得部分分。
例如：《夹缝中求和》（来源牛客IOI周赛普及组20-D）
https://ac.nowcoder.com/acm/contest/8997/D
给定一个数组a，以及两个正整数x 和y ，求取两个数ai和aj （i<j），满足x≤ai+aj≤y的取法有多少种？
注：只要两个取法有一个角标不同
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
算法笔面试宝典 文章被收录于专栏
算法笔面试真题解析
