- [贪心算法](./advanced_algorithm/greedy.md)

- [贪心算法](advanced_algorithm/greedy.md)

贪心算法在每一步选择中都采取在当前状态下最好或最优的选择，从而使得结果也是最优解，适合去解决具有最优子结构的问题。

最优子结构的特征：

- 每一次操作对结果直接产生影响

- 不依赖于之前的操作

- 子问题的最优解是全局最优解的一部分

思路：每个格子`i`作为起跳点最远能跳到`nums[i]`处，所以遍历数组得到最远距离并与数组长度进行比较即可。

这题只需要判断能否到达终点而无需给出具体路径，所以不需要用回溯的方法。

public boolean canJump(int[] nums) {

int maxLen = 0;

for (int i = 0; i < nums.length; i++) {

// 当前格子已经无法跳到

if (i > maxLen) return false;

// 更新能跳到的最远距离

maxLen = Math.max(maxLen, i + nums[i]);

}

return true;

}

思路：确保每次跳跃选择的格子都有最远的跳跃范围。

public int jump(int[] nums) {

int steps = 0;

int start = 0;

int end = 1;

while (end < nums.length) {

// 确定最远的跳跃范围

int maxPosition = 0;

for (int i = start; i < end; i++) {

maxPosition = Math.max(maxPosition, i + nums[i]);

}

start = end;

end = maxPosition + 1;

// 步数增加

steps++;

}

return steps;

}

思路：先排序，再贪心，让饼干优先满足胃口更多的孩子

public int findContentChildren(int[] g, int[] s) {

Arrays.sort(g);

Arrays.sort(s);

int p = 0;

int q = 0;

while (p < g.length && q < s.length) {

if (g[p] <= s[q]) {

p++;

}

q++;

}

return p;

}