403. Frog Jump

https://leetcode.com/problems/frog-jump/description/

给一个数组，元素的值代表横轴的坐标，从0点起跳可跳一步远，以后只要上次跳了k-1, k 或k+1步, 那本次就可以跳k步，问能否跳到最后一个元素代表的位置。问能否跳到解法无非DP或greedy。action为从前面的任一位置j跳到当前位置i，i和j的距离为k, action成功与否受限于跳到上一位置j 是否用了k-1, k或k步。因此状态记录对于位置i, 所有可能的k。

/*
 * @lc app=leetcode id=403 lang=cpp
 *
 * [403] Frog Jump
 *
 * https://leetcode.com/problems/frog-jump/description/
 *
 * algorithms
 * Hard (36.87%)
 * Likes:    601
 * Dislikes: 72
 * Total Accepted:    59.3K
 * Total Submissions: 160.1K
 * Testcase Example:  '[0,1,3,4,5,7,9,10,12]'
 *
 * A frog is crossing a river. The river is divided into x units and at each
 * unit there may or may not exist a stone. The frog can jump on a stone, but
 * it must not jump into the water.
 * 
 * Given a list of stones' positions (in units) in sorted ascending order,
 * determine if the frog is able to cross the river by landing on the last
 * stone. Initially, the frog is on the first stone and assume the first jump
 * must be 1 unit.
 * 
 * 
 * If the frog's last jump was k units, then its next jump must be either k -
 * 1, k, or k + 1 units. Note that the frog can only jump in the forward
 * direction.
 * 
 * Note:
 * 
 * The number of stones is ≥ 2 and is < 1,100.
 * Each stone's position will be a non-negative integer < 2^31.
 * The first stone's position is always 0.
 * 
 * 
 * 
 * Example 1:
 * 
 * [0,1,3,5,6,8,12,17]
 * 
 * There are a total of 8 stones.
 * The first stone at the 0th unit, second stone at the 1st unit,
 * third stone at the 3rd unit, and so on...
 * The last stone at the 17th unit.
 * 
 * Return true. The frog can jump to the last stone by jumping 
 * 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 
 * 2 units to the 4th stone, then 3 units to the 6th stone, 
 * 4 units to the 7th stone, and 5 units to the 8th stone.
 * 
 * 
 * 
 * Example 2:
 * 
 * [0,1,2,3,4,8,9,11]
 * 
 * Return false. There is no way to jump to the last stone as 
 * the gap between the 5th and 6th stone is too large.
 * 
 * 
 */
class Solution {
public:
    bool canCross(vector<int>& stones) {
        const int N = stones.size();
        vector<unordered_set<int>> dp(N);
        dp[0].insert(0);
        for (int i = 1; i < N; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                int k = stones[i] - stones[j];
                if (k >= N) break;
                if (dp[j].count(k - 1) || dp[j].count(k) || dp[j].count(k + 1)) {
                    dp[i].insert(k);
                }
                if ((i == N - 1) && dp[i].count(k)) return true;
            }
        }
        return false;
    }
};