# C++ recursive dp solution

• ``````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);
}
};
``````

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