青蛙过河

Category Difficulty Likes Dislikes
algorithms Hard (45.80%) 447 -
Tags

Companies

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

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

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

示例 1：

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

示例 2：

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

提示：

  • 2 <= stones.length <= 2000
  • 0 <= stones[i] <= 231 - 1
  • stones[0] == 0
  • stones 按严格升序排列

动态规划(c++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem403.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=403 lang=cpp
 *
 * [403] 青蛙过河
 */

// @lc code=start

/** 
 * 动态规划
 * 0 1 3 5 6 8 12 17
 * n = stones.size()
 * f[0] = true;  f[(1~n)] = f[(1~n)-1] && stones[(1~n)-1]-stones[(1~n)-2]+1+stones[(1~n)-1] >= stones[(1~n)]
 * 边界：n < 3 return stones[0] == 0 && stones[1] == 1 ? 
 * 
 * [0,1,3,5,6,8,12,17]
 * 0-1 1-3 3-5 5-8 8-12 12-17
 * i = (2~n-2) f=[n][2] f[i][0] = stones[i] < f[i-1][1] ? min(f[i-1][0],stones[i]-stones[i-1]) : min(stones[i+1]-stones[i], stones[i]-stones[i-1]);
 * f[i][1] = f[i][0] + stones[i] + 1;
 * 
 */

class Solution {
public:
    bool canCross(vector<int>& stones) {
        int n = stones.size();
        // if (n < 3) {
        //     return n == 2 ? 
        // }
        // if (stones[0] != 0 || stones[1] != 1) return false;
        // vector<vector<int>> f(n, vector<int>(2, 0));
        // f[0][0] = f[0][1] = 1;
        // for (int i = 1; i < n-1; ++i) {
        //     f[i][0] = stones[i] < f[i-1][1] ? f[i-1][0] : min(stones[i+1]-stones[i], stones[i]-stones[i-1]);
        //     if (stones[i+1] - 1 > f[i][0] + stones[i]) {
        //         return false;
        //     }
        //     f[i][1] = f[i][0] + stones[i] + 1;
        // }
        // return true;
        // vector<int> f(n, 0);
        // f[0] = 1;
        // for (int i = 1; i < n - 1; ++i) {
        //     f[i] = max(f[i], stones[i] - stones[i-1]);
        //     if (stones[i] + f[i] > stones[i+1] - 1 && !f[i+1]) {
        //         f[i] = stones[i] - stones[i-1];
        //     }
        //     int j = i+1;
        //     while (j < n && stones[j] - 1 <= f[i] + stones[i]) {
        //         if (stones[j] + 1 > stones[i] + f[i])
        //             f[j] = max(f[j], stones[j] - stones[i]);
        //         ++j;
        //     }
        //     if (f[n-1]) { 
        //         return true;
        //     }
        //     if ((stones[i] + f[i] < stones[i+1] - 1) || ((stones[i] + f[i] > stones[i+1] + 1) && stones[i] * 2 - stones[i-1] > stones[i+1] + 1 && !f[i+1])) {
        //         return false;
        //     }
        // }
        // return true;
        vector<vector<bool>> f(n, vector<bool>(n, false));
        f[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;
                }
                f[i][k] = f[j][k-1] || f[j][k] || f[j][k+1];
                if (i == n - 1 && f[i][k]) {
                    return true;
                }
            }
        }
        return false;

    }
};
// @lc code=end