描述
给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
数组A的长度不超过20000，每个元素的大小不超过20000
样例
样例 1：
输入：
A = [2,3,1,1,4]
输出：
2
解释：
到达最后位置的最小跳跃次数是2(从下标0到1跳跃1个距离长度，然后跳跃3个距离长度到最后位置)
解题思路这道题是典型的贪心算法，通过局部最优解得到全局最优解。有两种方法使用贪心算法实现，只是贪心的策略不同。
目标是到达数组的最后一个位置，因此我们可以考虑最后一步跳跃前所在的位置，该位置通过跳跃能够到达最后一个位置。
如果有多个位置通过跳跃都能够到达最后一个位置，可以「贪心」地选择距离最后一个位置最远的那个位置，也就是对应下标最小的那个位置。因此，我们可以从左到右遍历数组，选择第一个满足要求的位置。
找到最后一步跳跃前所在的位置之后，继续贪心地寻找倒数第二步跳跃前所在的位置，以此类推，直到找到数组的开始位置。
使用这种方法编写的 C++ 和 Python 代码会超出时间限制。
题解代码
java
1public class Solution {
2
6 public int jump(int[] a) {
7 // write your code here
8 int position = a.length - 1;
9 int steps = 0;
10 while (position > 0) {
11 for (int i = 0; i < position; i++) {
12 if (i + a[i] >= position) {
13 position = i;
14 steps++;
15 break;
16 }
17 }
18 }
19 return steps;
20 }
21}
复杂度分析
-
时间复杂度：O(n^2)O(n2)，其中 nn 是数组长度。有两层嵌套循环，在最坏的情况下，例如数组中的所有元素都是 11，position 需要遍历数组中的每个位置，对于 position 的每个值都有一次循环。
-
空间复杂度：O(1)O(1)。
描述
给定字符串 s 和单词字典 dict，确定 s 是否可以分成一个或多个以空格分隔的子串，并且这些子串都在字典中存在。
因为我们已经使用了更强大的数据，所以普通的DFS方法无法解决此题。
样例
样例 1：
输入：
s = "lintcode" dict = ["lint", "code"]
输出：
true
解释：
lintcode可以分成lint和code。
样例 2：
输入：
s = "a" dict = ["a"]
输出：
true
解释：
a在dict中。
使用《九章算法班》中讲过的划分型动态规划算法
- state: dp[i] 表示前 i 个字符是否能够被划分为若干个单词
- function: dp[i] = or{dp[j] and j + 1~i 是一个单词}
java
1public class Solution {
2
7 public boolean wordBreak(String s, Set dict) {
8 if (s == null) {
9 return true;
10 }
11
12 int maxLength = 0;
13 for (String word : dict) {
14 maxLength = Math.max(maxLength, word.length());
15 }
16
17 int n = s.length();
18 boolean[] dp = new boolean[n + 1];
19 dp[0] = true;
20
21 for (int i = 1; i <= n; i++) {
22 for (int l = 1; l <= maxLength; l++) {
23 if (i < l) {
24 break;
25 }
26 if (!dp[i - l]) {
27 continue;
28 }
29 String word = s.substring(i - l, i);
30 if (dict.contains(word)) {
31 dp[i] = true;
32 break;
33 }
34 }
35 }
36
37 return dp[n];
38 }
39} 
