Frog Jump

LeetCode #403

Description:

Example:

Note

Idea:

DFS+DP，状态是当前location和上一步step。用DP来加速。

Code:

class Solution {
public:
    bool canCross(vector<int>& stones) {
        unordered_map<string, bool> memo;

        return DFS(stones, 0, 0, memo);
    }

    bool DFS(vector<int>& stones, int indx, int step, unordered_map<string, bool>& memo){
        // cout<<indx<<' '<<step<<endl;
        if(indx==stones.size()-1) return true;
        // 用string来当key，记录现在的location和上一步step
        string loc_step=to_string(indx) + to_string(step);

        if(memo.find(loc_step)!=memo.end()) return memo[loc_step];

        bool success=false;
        for(int next_step = step-1; next_step <= step+1; next_step++){
            for(int i=indx; i<stones.size(); ++i){
                if(next_step>0 && stones[indx]+next_step==stones[i]){
                    // 只要一个能走通就OK
                    success = success||DFS(stones, i, next_step, memo);
                }
            }
        }
        memo[loc_step]=success;
        return memo[loc_step];
    }
};