ref
记忆化搜索,f[i][j] 表示在stones的第i个位置,可以跳j距离,是否可以跳到最后
C++ 代码
class Solution {
public:
bool canCross(vector<int>& stones) {
int n = stones.size();
stones_ = stones;
for(int i=0; i<stones.size(); ++i) stones_index_[stones[i]] = i;
f_ = vector<vector<int>>(n, vector<int>(n+1, -1));
f_[0][1] = 1;
// 枚举最后一个位置的状态
for(int i=0; i<=n; ++i) {
if(dp(n-1, i)) return true;
}
return false;
}
private:
vector<int> stones_;
unordered_map<int,int> stones_index_;
vector<vector<int>> f_;
int dp(int i, int j) {
if(f_[i][j] != -1)return f_[i][j];
f_[i][j] = 0;
for(int k=max(1, j-1); k<=j+1 && k<=(int)stones_.size(); ++k) {
int last = stones_[i] - k;
if(stones_index_.count(last)) {
int last_i = stones_index_[last];
if(dp(last_i, k)) {
f_[i][j] = 1;
break;
}
}
}
return f_[i][j];
}
};