力扣 403 青蛙过河

题意：给定一个石头array，判定青蛙能否跳到最后一个石头

思路：

1. 把stone的位置放入set
2. 用两个stack，分别记录当前可跳到的位置，和跳到该位置的上一跳的步数
3. 遍历stack，以及当前stack头部节点，并把它所能到达的stone加入stack，如果这个过程中遇到了最后一个stone返回true
4. 否则返回false

思想：动态规划

复杂度：时间O（n^2)，空间O(n)

class Solution {
    public boolean canCross(int[] stones) {
        
        for(int i=3;i<stones.length;i++)
        {
            if(stones[i] > stones[i-1] * 2)
            {
                return false;
            }
        }
        HashSet<Integer> hs = new HashSet<Integer>();
        for(int stone:stones)
        {
            hs.add(stone);
        }
        
        
        Stack<Integer> positions = new Stack<Integer>();
        Stack<Integer> jumpCounts = new Stack<Integer>();
        
        positions.add(0);
        jumpCounts.add(0);
        
        
        while(!positions.isEmpty())
        {
            int jump = jumpCounts.pop();
            int pos = positions.pop();
            
            for(int i=jump-1;i<=jump+1;i++)
            {
                if(i<=0)
                {
                    continue;
                }

                if(pos + i == stones[stones.length-1])
                {
                    return true;
                }
                else if(hs.contains(pos+i))
                {
                    positions.add(pos+i);
                    jumpCounts.add(i);
                }
                
            }
            
        }
        return false;
        
    }
}