C++ recursive dp solution


  • 0
    W
    struct pos {
    	int start;
    	int k;
    };
    bool operator<(const pos& me, const pos& other) {
    	if (me.start != other.start) return me.start < other.start;
    	return me.k < other.k;
    }
    class Solution {	
    	bool canCross(unordered_set<int>& units, map<pos, bool>& flags, int end, int start, int k) {
    		if (start == end) {
    			return true;
    		}
    		if (k - 1 > 0 && start + k - 1 <= end && units.count(start + k - 1)) {
    			auto it = flags.find({ start + k - 1, k - 1 });
    			if (it == flags.end()) {
    				bool can = canCross(units, flags, end, start + k - 1, k - 1);
    				if (can) {
    					return true;
    				}
    			}
    		}
    		if (start + k <= end && units.count(start + k)) {
    			auto it = flags.find({ start + k, k });
    			if (it == flags.end()) {
    				bool can = canCross(units, flags, end, start + k, k);
    				if (can) {
    					return true;
    				}
    			}
    		}
    		if (start + k + 1 <= end && units.count(start + k + 1)) {
    			auto it = flags.find({ start + k + 1, k + 1 });
    			if (it == flags.end()) {
    				bool can = canCross(units, flags, end, start + k + 1, k + 1);
    				if (can) {
    					return true;
    				}
    			}
    		}
    		flags[{start, k}] = false;
    		return false;
    	}
    public:
    	bool canCross(vector<int>& stones) {
    		if (stones.size() < 2 || stones.size() >= 1100 || stones[1] != 1) return false;
    		unordered_set<int> units(stones.begin(), stones.end());
    		map<pos, bool> flags;
    		return canCross(units, flags, stones.back(), 1, 1);
    	}
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.