贪心算法（又称贪婪算法，最优子结构）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
1. 分发饼干（455 简单）
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子
i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。每人只发一块饼干，为了尽可能满足最多数量的孩子，从贪心的角度考虑，应该按照孩子的胃口从小到大的顺序依次满足每个孩子，且对于每个孩子，应该选择可以满足这个孩子的胃口且尺寸最小的饼干。
示例 1:
示例 2:
代码实现：
跳跃游戏（55 中等）
贪心 数组 动态规划
给你一个非负整数数组
nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标，如果可以，返回
true ；否则，返回 false 。示例 1：
示例 2：
解法：倒序遍历，核心在于如何跳过0，当前0始终跳不过则为False。用flag标记状态，默认为True，如果遍历到0就变False，并记录0下标，然后查看后面元素能否跳过标记0的下标位置。
代码实现：
跳跃游戏（45 中等）*
贪心 数组 动态规划
给定一个长度为
n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素
nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:0 <= j <= nums[i]
i + j < n
返回到达
nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。示例 1:
示例 2:
三种思路：动态规划、动态规划+贪心、+贪心
代码实现：
贪心：
1. 首先明确第i个位置下次跳的范围为：i+1, nums[i] +i
2. 几个变量：end当前能达到的最远；max_pos下次能跳到的最远位置；steps最少跳跃次数（最终输出）
3. 思路：一次遍历，看下nums[i] +i 和max_pos谁最大，然后传递给max_pos。当i==end时，用max_pos更新end
动态规划：
1. 定义状态列表
dp = len(nums)*float(”inf”) ,dp[i]表示跳到下标i所需要的最小跳跃次数。2. 状态转义方程：
对于当前位置 i，如果之前的位置 j（0≤j<i0 \le j < i0≤j<i） 能够跳到位置 i 需要满足：位置 j（0≤j<i0 \le j < i0≤j<i）加上位置 j 所能跳到的最远长度要大于等于 i，即 j + nums[j] >= i 。而跳到下标 i 所需要的最小跳跃次数则等于满足上述要求的位置 j 中最小跳跃次数加 1，即
dp[i] = min(dp[i], dp[j] + 1)。- 初始条件
初始状态下，跳到下标
0 需要的最小跳跃次数为 0，即 dp[0] = 0。打家劫舍（LCR 89 中等）
数组 动态规划
最长公共子序列（LCR 095 中等）
给定两个字符串
text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
