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）
[限制] 必须刚好跳到石头上，如果跳力太强，超过了石头，算掉在水里
[图释]
![]()
