455. | 贪心算法 LeetCode

分析：

  贪心思想的核心是每一步只考虑当前的最优解，这些最优解构成最终问题的解。与动态规划不容，当前的最优解是独立的，与上下文无关。所以贪心算法需要满足其最优解能够由其子问题的最优解组成，也就是该问题具有最优子结构性质。

  具体到这一题。首先，小孩之间的饥饿感互不影响，一个人饱了其他人不会跟着变饱，其子问题是独立的。其次，每一次只要用最小的饼干喂饱胃口最小的那个小孩（子最优解），就能喂饱最多小孩，即问题的最优解。

  这里，可以用数学归纳法来证明贪心算法对该题有效。（不严谨证明，有错的话可以指正）

• 当child = 1, cookie = 1时，显然结论成立。

• 假设当child=1,2,...,n,  cookie=1,2,...,m时，结论也成立。则当child = 1,2,...,n,n+1, cookie=1,2,...,m,m+1时，若拿m+1饼干去喂n+1之前的小孩k，则n+1小孩一定无法喂饱，也就是比m+1喂n+1的结果小，反证了对n+1,m+1的情况，该结论也成立。

• 即对该问题，每一次只要用最小的饼干喂饱胃口最小的那个小孩，就能喂饱最多小孩。
  

  因此，我们需要先对两个数组进行排序，然后依次喂饱小孩，直到所有饼干都喂完或没有满足的饼干为止。