坐标型--（b）跳格子

---

1) jump game I, II (LeetCode 55, 45)

[ 要求] 给出jump power数组，

I	II
看能否从数组头跳到数组尾（T or F）	看从数组头跳到数组尾的最少步数

[限制] 跳的距离是正数

[图释]

[图释]

[复杂度] 时间 O(n^2), 空间 O(n)

---

2) climbing stairs (LeetCode 70)

[要求] 从起点一次跳1或2格，一共跳n格，求到达终点的跳法数

[坑] 一共跳n格，代表有n+1个格子

[图释]

[复杂度] 时间 O(n), 空间 O(n) --> O(3) //使用滚动数组

---

3) word break I (LeetCode 139)

[要求] 字符串S能否分解成若干个子串和（这些子串要在字典中出现）

[坑] 对于字符串问题，f[]要多扩展一位，用f[0]代表空串

[图释]

[复杂度] 时间 O(nn), 空间 O(n)

---

4) perfect squares (LeetCode 279)

[要求] 把数字n分解成平方数(1^2, 2^2, 3^2, 4^2...，即1,4,9,16...)之和，求最少的分解项数

[举例] 4可以分解为4=1^2 + 1^2 + 1^2 + 1^2 ,一共4项（不是答案）。也可以分解为4=2^2，一共1项（这是答案）

[分析] 相当于怎样从整数0能用最少的步数跳到整数n的问题。（中间的跳力是1或4或9或16...）。

[图释]

[复杂度] 时间 O(n*sqrt(n)), 空间 O(n)

---

5) frog jump (LeetCode 403)

[要求] 看青蛙能否从第一块石头跳到最后一块石头（T or F）

[限制] 必须刚好跳到石头上，如果跳力太强，超过了石头，算掉在水里

[图释]

[复杂度] 时间 O(n * n * n), 空间 O(n * n)