每日一题 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;
    }
};

原文地址：https://blog.csdn.net/qq_42376925/article/details/145099611

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！