[数据结构与算法]LeetCode 403. 青蛙过河

一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。

给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃 1 个单位（即只能从单元格 1 跳至单元格 2 ）。

如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。

暴力、暴力

const int N = 2010;
class Solution {
public:
    bool f[N][N];
    bool dfs(vector<int>& stones, int u, int k)
    {
        if(f[u][k]) return false; //已经搜索过了，不用搜索了

        if(u == stones.size() - 1)  return true;

        f[u][k] = true;
        int a = stones[u] + k  + 1;
        for(int j = u + 1; stones[j] <= a && j < stones.size(); j ++)
        {
            int b = stones[j] - stones[u];
            if(b >= k - 1 && b <= k + 1)
                if(dfs(stones, j, b)) 
                    return true;
        }
        return false;
    }
    bool canCross(vector<int>& stones) {

        return dfs(stones, 0, 0);

    }
};