青蛙跳完台阶又去过河了

类似的，每一次可以选择上一次的距离K的K-1、K、K+1,的距离进行前进。直到到达终点

1.回溯求解（内存超出）

class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> temp = new ArrayList<>();
    public boolean canCross(int[] stones) {
        if(stones[1] == stones[0] + 1){
            dfs(stones, 1, stones[1]);
            // System.out.println(ans);
            if(ans.size() == 0) return false;
            else return true;
        }else{
            return false;
        }
    }
    private boolean que(int[] stones, int k){
        for(int i=0;i<stones.length;i++){
            if(k == stones[i]){
                return true;
            }
            if(stones[i] > k) return false;
        }
        return false;
    }
    private void dfs(int[] stones,int k,int cur){
        if(k==0 || !que(stones, cur)){//后面的数组不存在我们下一个落脚点,或者k=0
            return;
        }
        if(cur == stones[stones.length-1]){//下一步可以到达最后一个石头
            ans.add(new ArrayList<Integer>(temp));
            return;
        }
        int[] chose = {-1, 0, 1};
        for(int i=0;i<3;i++){
            temp.add(k+chose[i]);
            dfs(stones,k+chose[i], cur+k+chose[i]);
            temp.remove(temp.size() - 1);
        }
    }
}

2.动态规划

public class Solution {
    public boolean canCross(int[] stones) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for(int i=0;i<stones.length;i++){
        	map.put(stones[i], new HashSet<Integer>());
    }
    map.get(0).add(0);
    for(int i=0;i<stones.length;i++){
    	for(int k:map.get(stones[i])){
    		for(int j=k-1;j<=k+1;j++){
    			if(j > 0 && map.containsKey(stones[i]+j)){
    				map.get(stones[i]+j).add(j);
    			}
    		}
    	}
    }
    return map.get(stones[stones.length-1]).size() > 0;
    }
}

最后

以上就是唠叨春天为你收集整理的青蛙跳完台阶又去过河了的全部内容，希望文章能够帮你解决青蛙跳完台阶又去过河了所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。