青蛙过河

算法1

第一次提交，超时

用循环，老师说是因为力扣评判不太标准，正常情况下n=2000，O(n2)是可以的。但是力扣这里要用记忆化搜索写

class Solution {
public:

    bool dfs(vector<int>& stones, int index, int k){
        int n = stones.size();
        int nextindex = -1;
        bool flag;
        if(index == n-1) flag = true;
        else{
            for(int i = index+1; i < n; i++){
                if(stones[index] + k == stones[i]){
                    nextindex = i;
                    flag = dfs(stones, nextindex, k-1) || dfs(stones, nextindex, k) || dfs(stones, nextindex, k+1);
                }
            } 
            if(nextindex == -1) flag = false;            
        }
        //return true;
        //return false;   
        return flag;    
    }

    bool canCross(vector<int>& stones) {
        if(stones[1] != 1) return false;
        return dfs(stones, 1, 0) || dfs(stones, 1, 1) || dfs(stones, 1, 2);
    }
};

算法2

这里查了别的方法，比我的思路多了一个map 仍然超时。它的答案也超时。

map.count(Key)返回值为1或者0，1返回存在，0返回不存在，返回的是布尔类型的值，因为在map类型中所有的数据的Key值都是不同的，所以被count的数要么存在1次，要么不存在

https://blog.csdn.net/guangcheng0312q/article/details/116279795

class Solution {
public:
    unordered_map<int, int> hash;

    bool dfs(vector<int>& stones, int n, int index, int k){
        if(index == n-1) return true;
        for(int i = -1; i <= 1; i++){
            if(k + i == 0) continue;
            int next = stones[index] + k + i;
            if(hash.count(next)){ //坐标存在
                if(dfs(stones, n, hash[next], k+i)){
                    return true;
                } 
            }
        } 
        return false;
    }

    bool canCross(vector<int>& stones) {
        for (int i = 0; i < stones.size(); i++) {
            hash[stones[i]] = i;  // key:石子值 value是第几块石子
        }
        if(!hash.count(1)) return false;
        int n = stones.size();
        return dfs(stones, n, 1, 1);
    }
};

算法3

在算法2的基础上增加记忆化搜索，使用数组f[][].通过

class Solution {
public:
    unordered_map<int, int> hash;
    int f[2010][2010];

    bool dfs(vector<int>& stones, int n, int index, int k){
        if(f[index][k] != -1) return f[index][k];
        if(index == n-1) return f[index][k] = 1;
        for(int i = -1; i <= 1; i++){
            if(k + i == 0) continue;
            int next = stones[index] + k + i;
            if(hash.count(next)){ //坐标存在
                if(dfs(stones, n, hash[next], k+i)){
                    return f[index][k] = 1;
                } 
            }
        } 
        return f[index][k] = false;
    }

    bool canCross(vector<int>& stones) {
        for (int i = 0; i < stones.size(); i++) {
            hash[stones[i]] = i;  // key:石子值 value是第几块石子
        }
        if(!hash.count(1)) return false;
        memset(f, -1, sizeof(f));
        int n = stones.size();
        return dfs(stones, n, 1, 1);
    }
};

算法4

动态规划.通过

class Solution {
public:

    int dp[2010][2010];

    bool canCross(vector<int>& stones) {
        int n = stones.size();
        if (stones[1] != 1) return false;
        dp[1][1] = 1; //dp[i][k]表示位于第i个位置，前进k步到达i
        for(int i = 1; i < n; i++){
            for(int j = 1; j < i; j++){
                int k = stones[i] - stones[j];
                if(k > j+1) continue;
                dp[i][k] = dp[j][k-1] || dp[j][k] || dp[j][k+1];
            }
        }
        for(int i = 1; i < n; i++){
            if(dp[n-1][i]) return true;
        }
        return false;
    }
};