find alibaba

面试官说是道新题 finding ali baba就是ali baba是个怪兽，他可能在[0，1, ..., numCaves-1]出现，他每隔一天就要换一个地方，但他每次只能移左右一格。 然后给你一个strategy[]数组，数组里面是猜测每天ali baba的位置。如果里面有一个 猜中了，这个strategy就是正确的。问题就是让你写一个判断函数 alibaba(int numCaves, int[] strategy)来判别这个strategy数组是不是稳赢的策略。写完后问时间复杂度，然后问了下大概怎么样可以优化～～～

来自链接：http://www.mitbbs.com/article_t1/JobHunting/32978937_0_1.html 感觉挺难的，很难看懂。n * k 的matrix cut branch压根不知道讲的什么意思。DP还好理解些，希望老师和同学们能够给出详细的解释，多谢啦

import java.io.*;
import java.util.*;
/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

class Solution {

  private boolean canCatch(int n, int[] strategy) {
    if (n <= 1) return true;
    int m = strategy.length;
    boolean dp[][] = new boolean[m][n];
    dp[0][strategy[0]] = true;
    for (int i = 1; i < m; i++) {
      boolean escape = false;
      for (int j = 0; j < n; j++) {
        boolean pre = true;
        boolean next = true;
        if (j != 0) {
          pre = dp[i - 1][j - 1];
        }
        if (j != n - 1) {
          next = dp[i - 1][j + 1];
        }
        dp[i][j] = (pre && next) || strategy[i] == j;
        if (!dp[i][j]) escape = true;
      }
      if (!escape) return true;
    }
    return false;
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.canCatch(7, new int[] {1,2,3,0,3,4,5,5,4,3,6,3,2,1}));
    System.out.println(s.canCatch(7, new int[] {1,2,3,3,4,5,5,4,6,4,3,2,1}));
    System.out.println(s.canCatch(4, new int[] {2, 1, 1, 2}));
    System.out.println(s.canCatch(7, new int[] {1,2,3,3,4,5,5,4,6,4,3,2,1}));
 
 
 
//     s.printAllCombine(new char[] {'a', 'b', 'c', 'd'}, 3);
//     {'a', 'b', 'c'}, 有一个整数值K，如果K＝2，输出aa,ab,ac,ba,bb,bc,ca,cb,cc?
 
  }
}

=========

import java.io.*;
import java.util.*;
/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

class Solution {
 
  private boolean canCatch(int n, int[] strategy) {
    if (n <= 1) return true;
    int m = strategy.length;
    boolean dp[] = new boolean[n];
    dp[strategy[0]] = true;
    for (int i = 1; i < m; i++) {
      boolean escape = false;
      boolean old = false;
      for (int j = 0; j < n; j++) {
        boolean pre = true;
        boolean next = true;
        if (j != 0) {
          pre = old;
        }
        if (j != n - 1) {
          next = dp[j + 1];
        }
        old = dp[j];
        dp[j] = (pre && next) || strategy[i] == j;
        if (!dp[j]) escape = true;
      }
      if (!escape) return true;
    }
    return false;
  }
 
  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.canCatch(7, new int[] {1,2,3,0,3,4,5,5,4,3,6,3,2,1}));
    System.out.println(s.canCatch(7, new int[] {1,2,3,3,4,5,5,4,6,4,3,2,1}));
    System.out.println(s.canCatch(4, new int[] {2, 1, 1, 2}));
    System.out.println(s.canCatch(7, new int[] {1,2,3,3,4,5,5,4,6,4,3,2,1}));
   
   
   
//     s.printAllCombine(new char[] {'a', 'b', 'c', 'd'}, 3);
//     {'a', 'b', 'c'}, 有一个整数值K，如果K＝2，输出aa,ab,ac,ba,bb,bc,ca,cb,cc?
   
  }
}