Find Alibaba

/*
就是ali baba是个怪兽，他可能在[0，1, ..., numCaves-1]出现，他每隔一天就要换
一个地方，但他每次只能移左右一格。
然后给你一个strategy[]数组，数组里面是猜测每天ali baba的位置。如果里面有一个
猜中了，这个strategy就是正确的。
问题就是让你写一个判断函数 alibaba(int numCaves, int[] strategy)来判别这个
strategy数组是不是稳赢的策略。写完后问时间复杂度，然后问了下大概怎么样可以优
化
*/
public class FindAlibaba {
    
// 可以用 res[i][j] 来表示 第j天在Cave i能不能捉到alibaba. 如果捉到，则为true, 否则为false
// 然后状态转换方程就是res[i][j] = res[i][j] || res[i - 1][j - 1] && res[i + 1][j - 1], 它的解依赖于往左跳一格和往右跳一格
// 然后最后再check res[i][days - 1]是不是全是true， 是的话就代表这个strategy稳赢
// 时间复杂度就是O(numCaves * len(strategy))
    
    public boolean alibaba(int numCaves, int[] strategy) {
        int days = strategy.length;
        boolean[][] res = new boolean[numCaves][days];
        for(int i=0; i<days; i++) {
            res[strategy[i]][i] = true;
        }
        
        for(int i=0; i<numCaves; i++) {
            for(int j=1; j<days; j++) {
                if(i == numCaves-1) {
                    res[i][j] = res[i][j] || res[i-1][j-1];
                } else if(i == 0) {
                    res[i][j] = res[i][j] || res[i+1][j-1];
                } else {
                    res[i][j] = res[i][j] || (res[i-1][j-1] && res[i+1][j-1]);
                }
            }
        }
        
   
        for(int i=0; i<numCaves; i++) {
            if(res[i][days-1] == false) {
                return false;
            } 
        }
        return true;
    }
}