跳跃游戏 1
［抄题］：
［思维问题］：
［一句话思路］：
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
- 由于要用iteration, 不能return, 每次都要对can数组进行操作
- 循环函数中不用return false, 因为最终能不能是can数组决定的
［二刷］：
［三刷］：
［四刷］：
［五刷］：
[五分钟肉眼debug的结果]：
［总结］：
［复杂度］：Time complexity: O() Space complexity: O()
［英文数据结构或算法，为什么不用别的数据结构或算法］：
［其他解法］：
［Follow Up］：
［LC给出的题目变变变］：
[代码风格] ：
跳跃游戏 2
［抄题］：
给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
［思维问题］：
以为要比大小：确实是要比大小
［一句话思路］：
用steps[i] = steps[j] + 1来记录步数
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
- steps[j]是从0开始往i靠近的 用j + A[j] >= i 表示角标能赶上
- steps[i]中只要有一个能赶上就足以break
［二刷］：
［三刷］：
［四刷］：
［五刷］：
[五分钟肉眼debug的结果]：
不理解原理
［总结］：
通过角标能不能赶上，最终完成对steps[i]的迭代
［复杂度］：Time complexity: O(n^2) Space complexity: O(n^2)
［英文数据结构或算法，为什么不用别的数据结构或算法］：
DP greedy一般不好随意出题，Google出题比较多。
［其他解法］：
greedy
［Follow Up］：
［LC给出的题目变变变］：
757. Set Intersection Size At Least Two 至少有两个交集：greedy
[代码风格] ：
public class Solution {
public int jump(int[] A) {
// state
int[] steps = new int[A.length];
// initialize
steps[0] = 0;
for (int i = 1; i < A.length; i++) {
steps[i] = Integer.MAX_VALUE;
}
// function
for (int i = 1; i < A.length; i++) {
for (int j = 0; j < i; j++) {
if (steps[j] != Integer.MAX_VALUE && j + A[j] >= i) {
steps[i] = Math.min(steps[i], steps[j] + 1);
}
}
}
// answer
return steps[A.length - 1];
}
}