Report: Jump Game I

经典的DP, Greedy问题

  • 学习了经典的DP
    • 还有local, global最优解DP
    • 以及变动边界的loop

题目

思考

first trial: fail

  • 状态: boolean F[i] 表示能否从起点到达position i.
  • 一开始我的optimally equation想错了: 我想的是: F[i] = F[k] && A[k]>= abs(k-i). 这里的k是0…A.length. 在一开始的test case可以过, 但是{5, 8, 3, 0, 6, 7, 9, 6, 3, 4, 5, 2, 0, 6, 2, 6, 7, 10, 8, 0}就错了. 应该是true, 但我返回false.
    • 这里有2个错误, 一开始我想的是会不会有先跳到远的, 然后跳回来近的, 再跳到终点. 实际上是不会的, 因为这里的A[i]表示的是从position i, 能跳的最远距离, 而不是能跳的距离(像大富翁). 所以k不应该loop全部node, 而是小于i的所有node.
    • 更严重的错误是: F[i]表示的是是否能从起点到达. 所以只要能到达, 就OK了. 也就是说: 只要true, 就停止loop. 这也是导致我的这个code fail的原因.

second trial: OK

  • 这一次, 我还是DP, 不过改好了optimally equation, 即只要发现F[i]==true就break loop.
  • 但是这时候的时间是O(n**2). 因为要loop每一个node, 每一个node的内循环最坏情况是loop完所有小于i的k. 所以n+n-1+n-2+...+1 = O(n^2). 而且空间是O(n).

third trial: Failed

  • 这里还是使用Greedy最好, 因为只要最远距离超过position就行了, 那就看每一步能跳到的最远距离就行了. 实现的时候是使用经典的: local/global optimal. 再次复习一下这种使用2个DP表来解决问题的DP方法. 即local DP记录: 以目前node出发能得到的最优解. Global则是记录历史到目前node位置能得到的最优解.
  • 还要复习一下Greedy, 我之前的理解不对:
    • 错误: 之前想的是, Greedy不就是从位置1跳最远距离, 例如跳到位置5, 然后再从位置5跳最远距离. 觉得这种Greedy太Greedy了. 很有可能, 位置5的A[5]=0. 那就没得跳了.
    • 实际上, Greedy是针对每一个node都考虑一遍Greedy. 即: 1-5, 2-4-7, 3-9-dest.
  • 实现上面, Ganker只用了O(1)的空间. 我则是使用通用的DP表, 记录每一个node的state.
  • 代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    public static boolean jumpLocalGlobalDP(int[] A) {
        if (A == null || A.length == 0)
          return false;
        int[] local = new int[A.length];
        int[] global = new int[A.length];

        // init base condition
        local[0] = A[0];
        global[0] = A[0];

        // build the local/global DP table
        for (int i = 1; i < A.length; ++i) {
          local[i] = A[i] + i;
          global[i] = Math.max(global[i-1], local[i]);
        }

        // ans
        if (global[A.length-1] >= A.length - 1) {
          return true;
        }
        return false;
    }

Forth trial: AC

  • 刚才的做法是错误的, 例如{0,8,2,0,9}.
  • 仔细研究一下Ganker的写法, 他并不是简单的loop, 而是会改变boundary的loop. 这个很有意思. 在使用一个queue实现的BFS模版里面, 有个很重要的点就是queue.size()不能作为boundary, 要int size = queue.size(). 因为queue会在loop里面改变大小. 而这里之所以要使用变动的boundary是因为, 如果当前node只考虑能打到的情况. 例如这个例子里面, node 1是达不到的.
  • 所以很重要的一点是loop的范围应该是:
    1
    for (int i = 1; i <= global[i-1] && i < A.length; ++i)

Comments

▲ <<<<<<< Updated upstream ======= >>>>>>> Stashed changes <<<<<<< Updated upstream ======= >>>>>>> Stashed changes