LintCode 622 · Frog Jump(青蛙跳)

题目描述

动态规划组成部分一：确定状态

子问题

动态规划组成部分二：转移方程

动态规划组成部分三：初始条件和边界情况

动态规划四：计算顺序

Java代码实现

    public boolean canCross(int[] stones) {
    int n = stones.length;boolean[][] f = new boolean[n][n];f[0][0] = true;List<Integer> list = Arrays.stream(stones).boxed().collect(Collectors.toList());int index = -1;for (int i = 1; i < n; i++)for (int j = 1; j <= i; j++) {
    //这里不需要枚举石头i前的每一步，只需要对那些放有石头的坐标进行计算即可index = list.indexOf(stones[i] - j);if (index != -1) {
    f[i][j] |= f[index][j - 1] || f[index][j];if (j + 1 < n)f[i][j] |= f[index][j + 1];}}for (boolean b : f[n - 1])if (b)return b;return false;}

优化：动态规划加哈希表

Java代码实现

    public boolean canCross(int[] stones) {
    int n = stones.length;int t = 0;HashMap<Integer, HashSet<Integer>> f = new HashMap<>();for (int i = 0; i < n; i++)f.put(stones[i], new HashSet<>());f.get(stones[0]).add(0);for (int i = 0; i < n - 1; i++) {
    HashSet<Integer> tmp = new HashSet<>(f.get(stones[i]));for (int k : tmp)for (int j = -1; j <= 1; j++) {
    t = stones[i] + k + j;if (f.containsKey(t))f.get(t).add(k + j);}}return !f.get(stones[n - 1]).isEmpty();}

注意：

这里for循环一定要使用tmp，因为f在for循环里面是会变化的，所以要在for循环之前用tmp记录下来for循环之前的f.get(stones[i])。