【4.29】LeetCode每日一题· 青蛙过河

2021年04月29日 11时32分

标签： LeetCode 动态规划

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

给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。

开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格 1 跳至单元格 2 ）。

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

#### 示例1
```
输入：stones = [0,1,3,5,6,8,12,17]
输出：true
解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。
```

#### 示例2
```
输入：stones = [0,1,2,3,4,8,9,11]
输出：false
解释：这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。
```

#### 提示
```
2 <= stones.length <= 2000
0 <= stones[i] <= 2^31 - 1
stones[0] == 0
```

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/frog-jump "题目链接")

## 解题思路
题目描述中“状态转移”的特征十分明显（如果青蛙上一步跳跃了`k`个单位，那么它接下来的跳跃距离只能选择为`k - 1`、`k`或`k + 1`个单位）。所以可以用两个参数`dp[i, k]`表示状态，`i`表示当前青蛙跳到的石子编号，`k`表示上一次跳跃的长度。

状态转移方程也比较好写出。状态`dp[i, k]`可以从
`dp[j, k-1], dp[j, k], dp[j, k+1] (stones[i] - stones[j] == k)`三个状态转移过来，也就是说，如果当前青蛙在第`i`个石头上，前一次跳了`k`个单位，那么它必定是从距离第`i`个石头`k`个单位的石头`j`跳过来的，并且在跳跃到石头`j`的距离是`k-1`、`k`或者`k+1`。

问题的关键在于如何确定`k`的范围（自己解题的时候也卡在了这一步）。题目给出`k`的范围达到`2^31-1`，将其作为上界肯定会爆空间。题目中的一个重要结论可以给出答案：
** 如果当前青蛙在序号为i的石头上，则其最后一次跳跃的距离不会大于i，也就是在序号为i的石头上的青蛙，下一次跳跃的距离不会超过i+1**
证明：
* 由于青蛙只能向前跳且跳在石头上，因此每跳一次，石头序号必定增加大于等于1。也就是说，青蛙跳了`m`次后，所在的石头序号`i >= m`；
* 另一方面，青蛙每跳一次，跳跃的长度至多增加1（设青蛙还没跳时，之前一次跳跃的距离为0），因此，当青蛙跳了`m`次后，最后一次跳跃的距离`k <= m`
* 综上，有`k <= m <= i `，所以`k <= i`，命题得证。

所以，对于`n`个石头，最大的跳跃距离不会超过`n`（只有跳到第`n-1`个石头还需要跳），所以可以将状态限制在$$O(n^2)$$的范围内。

同时，由上述结论还可以得出两个可以对算法进行优化的点：
1. 如果存在两个相邻的石头，且`stones[i] - stones[i-1] > i`，则青蛙无法到达终点；（青蛙站在第i-1块石头上，其前一次跳跃距离小于等于i-1，从i跳到j的跳跃距离小于等于i，并且第i-1块石头是距离第i块石头最近的那一块石头。所以如果第i-1块石头到第i块石头的距离大于i，那么青蛙必定不能跳到最后一个单元格）
2. 当状态转移时，如果转移到当前状态的前一个状态`dp[j][·]`，与当前状态`dp[i][k]`的石头距离`k = stones[i] - stones[j] > j + 1`，则所有序号小于等于`j`的石头也不能转移状态`i`上。（序号更小的石头上，青蛙能跳的长度更小，但是距离却更长，更不可能转移到`dp[i][k]`的状态）

## 代码
```cpp
class Solution {
public:
    // dp[i][k] := 青蛙能否跳到第i块石头，且最后一次跳了k个单位
    // dp[i][k] = dp[j][k-1] | dp[j][k] | dp[j][k+1] where stone[i] - stone[j] == k;
    // dp[1][0] = dp[2][1] = true;
    // 重要结论：如果当前青蛙在序号为i的石头上，则其最后一次能跳跃的距离不会大于i
    bool canCross(vector<int>& stones) {
        const int n = stones.size();
        int dp[n][n];
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i < n; i++){
            // 青蛙站在第i-1块石头上，其前一次跳跃距离小于等于i-1，从i跳到j的跳跃距离小于等于i
            // 并且第i-1块石头是距离第i块石头最近的那一块石头
            // 所以如果第i-1块石头到第i块石头的距离大于i
            // 那么青蛙必定不能跳到最后一个单元格
            if(stones[i] - stones[i-1] > i) return false;
        }
        dp[0][0] = true;
        for(int i = 1; i < n; i++){
            for(int j = i-1; j >= 0; --j){
                int k = stones[i] - stones[j];
                if(k > j + 1) break;
                dp[i][k] = dp[j][k-1] || dp[j][k] || dp[j][k+1];
            }
        }
        bool res = false;
        for(int i = 0; i < n; i++){
            res = res || dp[n-1][i];
            if(res) return true; 
        }
        return false;
    }
};
```

### 用时和内存
> 执行用时：84 ms，在所有 C++提交中击败了83.98%的用户
> 内存消耗：27.2 MB，在所有 C++提交中击败了61.97%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【4.29】LeetCode每日一题· 青蛙过河

所有评论

暂无评论

新增评论