↓Skip to main content
  1. Posts/

LeetCode-403 青蛙过河

·1 min·
Table of Contents

LeetCode-403 青蛙过河 #

Solution 1 #

青蛙的状态有两个, 在第 $i$ 个石头上, 最后一步跳了 $j$ 步. 我们用 $dp[i][j]$ 来记录是否能够到达这一状态. 假设 $dp[i][j]$ 可以从第 $k$ 块石头转移而来, 那么必须是 $dp[k][stones[i] - stones[j] - 1], dp[k][stones[i] - stones[j]], dp[k][stones[i] - stones[j] + 1]$ 之一. 线性递推即可. 个别可以优化的点见代码.

代码如下:

class Solution {
public:
    bool canCross(vector<int>& stones) {
        int n = stones.size();
        vector<vector<int>> dp(n, vector<int>(n, false));
        dp[0][0] = true;
        for (int i = 1; i < n; i++) {
            if (stones[i] - stones[i - 1] > i) {
                return false;
            }
        }
        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];
                if (i == n - 1 && dp[i][k]) {
                    return true;
                }
            }
        }
        return false;
    }
};