-28 求解袋鼠过河问题（动态规划法） 分数 30 作者 王东 单位 贵州师范学院 求解袋鼠过河问题。一只袋鼠要从河这边跳到河对岸，河很宽，但河中间打了很多桩子，每隔一米就有一个，每个桩子上有一个弹簧，袋鼠跳到弹簧上就可以跳的更远。每个弹簧力量不同，用一个数字代表它的力量，如果弹簧的力量为5，就表示袋鼠下一跳最多能跳5米，如果为0，就表示会陷进去无法跳跃。河流一共n米宽，袋鼠初始在第一个弹簧上面，若跳到最后一个弹簧就算过河了，给定每个弹簧的力量，求袋鼠最少需要多少跳能够到达对岸。如果无法到达，输出-1。 函数接口定义： int solve();

这道题目可以使用动态规划算法来求解。我们可以定义一个状态数组dp，其中dp[i]表示袋鼠跳到第i个弹簧时最少需要的跳跃次数。对于每个弹簧，我们可以从前面的弹簧中选择一个能够跳到当前弹簧的最小跳跃次数，然后再加上当前弹簧的跳跃次数，即可得到跳到当前弹簧的最小跳跃次数。

注意，如果一个弹簧的力量为0，那么袋鼠无法跳到这个弹簧上，此时应该将dp数组中对应的值设置为一个很大的数，表示无法到达。

最后，如果dp数组中最后一个位置的值为一个很大的数，说明袋鼠无法到达对岸，此时应该返回-1，否则返回dp数组中最后一个位置的值。

下面是函数的具体实现：

const int INF = 0x3f3f3f3f;

int solve() {
    int n;
    cin >> n;
    vector<int> strength(n);
    for (int i = 0; i < n; i++) {
        cin >> strength[i];
    }
    vector<int> dp(n, INF);
    dp[0] = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (j + strength[j] >= i) {
                dp[i] = min(dp[i], dp[j] + 1);
            }
        }
    }
    return dp[n - 1] == INF ? -1 : dp[n - 1];
}