青蛙过河的动态规划方法-编程阁

一、问题描述

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

给定石子的位置列表 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;
}
};