题目描述：
一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。
给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃 1 个单位（即只能从单元格 1 跳至单元格 2 ）。
如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。
数据范围：
$2 \le stones.len \le 2000, 0 \le stones[i] \le 2^{31} - 1, stones[0] = 0$
严格升序
题解：
设计dp状态 $dp[i][j]$ 表示当前在 $i$ 下标，上一步跳了 $j$ 个单位，但是 $j$ 的范围不确定，可以使用 unordered_map。然后枚举上一步跳到了 $k, k\in [0, i)$ ，然后两者之间的距离是 $d = stones[i] - stones[k]$ ，如果 $dp[k][d - 1] \or dp[k][d] \or dp[k][d + 1]$ ，那么 $dp[i][d] = true$ 。
后续发现，每次最多比上一次多跳一个单位，因为 $0$ 是 $1$ ，则 $i$ 最多是 $i + 1$ 。可以直接使用二维数组，不用使用 unordered_map。
代码：
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
bool canCross(vector<int> &stones)
{
int n = stones.size();
if (stones[1] - stones[0] > 1)
return false;
if (n == 2)
return true;
vector<vector<int>> dp(n, vector<int>(n));
dp[1][1] = true;
for (int i = 2; i < n; ++i)
{
for (int j = i - 1; j >= 1; --j)
{
int k = stones[i] - stones[j];
if (k > j + 1)
continue;
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;
}
};
|