每日一题 403. 青蛙过河

403. 青蛙过河

动态规划，状态转移 和 上一步步长 和 当前位置点 有关系

class Solution {
public:bool canCross(vector<int>& stones) {int n = stones.size();unordered_map<int,unordered_set<int>> dp;unordered_map<int,int> mp;for(int i=0;i<n;++i){unordered_set<int> st;dp[i] = st;mp[stones[i]] = i;}dp[0].insert(0);for(int i=0;i<n;++i){for(int k : dp[i]){for(int jump : {k-1,k,k+1}){if(mp.count(jump+stones[i])){int idx = mp[jump+stones[i]];//cout<<i<<" "<<k<<" "<<jump+stones[i]<<endl;dp[idx].insert(jump);}}}}return dp[n-1].size() != 0;}
};