一、 问题描述
一只青蛙想要过河，河流被等分为若干个单元格，每个单元格内可能放有一块石子（也可能没有）。青蛙只能跳上石子，不能跳入水中。
给定石子的位置列表 stones（用单元格序号升序表示），需要判断青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。
约束条件：
1. 开始时，青蛙默认已站在第一块石子上
2. 第一步只能跳跃 1 个单位（从单元格 1 跳至单元格 2）
3. 如果青蛙上一步跳跃了 k 个单位，那么接下来的跳跃距离只能选择为 k-1、k 或 k+1 个单位
4. 青蛙只能向前方（终点方向）跳跃
二、解法思路
1. 状态定义
定义二维动态规划数组 `dp[i][speed]`，表示能否以 `speed` 的速度到达第 `i` 个石子。
`i`：石子的索引（0-based）
`speed`：到达第 `i` 个石子时的跳跃速度（即从上一次跳跃的距离）
2. 初始化
开始时，青蛙静止地站在 0 号石头上，因此： `dp[0][0] = 1`（表示可以以速度 0 到达起始位置）
3. 状态转移方程
对于每个石子 `i`，我们检查所有之前的石子 `j`（j < i），计算从 `j` 跳到 `i` 的速度：speed = stones[i] - stones[j]
如果能够从石子 `j` 以某种速度跳到石子 `i`，那么需要满足以下条件：
1. `speed > 0`（只能向前跳）
2. `speed ≤ j + 1`（速度不能超过 j+1，证明见后）
状态转移方程如下：
dp[i][speed] = dp[j][speed-1] || dp[j][speed] || dp[j][speed+1]
这意味着：如果从石子 `j` 出发，以 `speed-1`、`speed` 或 `speed+1` 的速度跳跃，可以到达石子 `j`，那么就可以以 `speed` 的速度到达石子 `i`。
4. 速度范围证明
为什么 `speed ≤ j + 1`？
假设青蛙从 0 号石子开始，每次跳跃速度最多增加 1。到达第 `j` 个石子时，最多进行了 `j` 次加速（从第一次跳跃开始计算），因此最大速度不会超过 `j`。那么从第 `j` 个石子起跳，最大速度不会超过 `j+1`。所以，从石子 `j` 跳到石子 `i` 的速度 `speed` 必须满足 `speed ≤ j+1`。
代码实现
cpp
class Solution {
public:
bool canCross(vector<int>& stones) {
int n = stones.size();
// dp[i][speed]: 表示能否以speed的速度，到达第i个石头
vector<vector<int>> dp(n, vector<int>(n+1, 0));
dp[0][0] = 1;
for(int i = 1; i < n; i++) {
for(int j = 0; j < i; j++) {
int speed = stones[i] - stones[j];
// 速度必须为正，且不能超过j+1
if(speed <= 0 || speed > j+1)
continue;
// 状态转移
dp[i][speed] = dp[j][speed-1] || dp[j][speed] || dp[j][speed+1];
// 如果已经到达最后一个石子，直接返回true
if(i == n-1 && dp[i][speed] == 1)
return true;
}
}
return false;
}
};
算法分析
时间复杂度
1.外层循环遍历所有石子：O(n)
2. 内层循环对于每个石子 i，遍历所有 j < i：O(n)
3. 总时间复杂度：O(n²)
空间复杂度
-dp数组大小为 n × (n+1)：O(n²)
性能表现
根据测试结果：
执行用时：320 ms（击败 23.86% 的 C++ 用户）
内存消耗：226.5 MB（击败 5.04% 的 C++ 用户）
总结
青蛙过河问题是一个典型的动态规划问题，通过定义合适的状态和状态转移方程，可以有效地解决。虽然基本的动态规划解法在时间复杂度和空间复杂度上都有优化空间，但它清晰地展示了问题的解决思路。
对于这类问题，关键点在于：
1. 正确理解问题约束条件
2. 设计合适的状态表示
3. 找到正确的状态转移关系
4. 注意边界条件的处理
