leetcode 403. 青蛙过河

一、题目

给定石子位置的列表stones（升序），青蛙可以跳上石子，但不能跳入水中。
如果青蛙一步跳跃了k个单位，那么它接下来跳跃的距离只能为k-1、k或k+1个单位。
青蛙只能向前方跳跃。

输入：

stones = [0,1,3,5,6,8,12,17]

输出：

true

解释：

青蛙可以成功过河，按照如下方案跳跃：
跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 
然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。

二、解法

思路：本题为二维动态规划，使用动态规划的方法，令dp[i][k]为跳跃k个单位能否到达第i个石子，初始化dp[0][0] = true;，得出状态转移方程dp[i][k] = dp[j][k-1] | dp[j][k] | dp[j][k+1];，其中j为上一次所在石子的编号。

2.1 动态规划

class Solution {
public:
    bool canCross(vector<int>& stones) {
        int n = stones.size();
        vector<vector<int>> dp(n, vector<int>(n));
        dp[0][0] = true;
        for (int i = 1; i < n; ++i) {
            if (stones[i] - stones[i - 1] > i) {  // 优化：跳跃距离k必定满足k <= i（可推），此时为青蛙无路可跳
                return false;
            }
        }
        for (int i = 1; i < n; ++i) {
            for (int j = i - 1; j >= 0; --j) {  // 反向枚举
                int k = stones[i] - stones[j];  // 跳跃的距离k，j为上一次所在石子的编号
                if (k > j + 1) {  // 在第j个石子上至多跳跃j+1的单位
                    break;
                }
                dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1];
                if (i == n - 1 && dp[i][k]) {
                    return true;
                }
            }
        }
        return false;
    }
};

复杂度分析

• 时间复杂度：O(n^2^)，n为石子的个数，第i个石子后方只有i-1个石子，因此在任意位置，青蛙的上一次跳跃距离至多只有n种，状态总数为 n^2^
• 空间复杂度：O(n^2^)，需要二维动态数组的空间，其中n是石子的数量