help me thank you

Question

题目描述
在一条数轴上，小明准备从起点0跳到终点n-1。

在数轴的每个点 i(0<=i<=n-1)上，都有一个限制跳跃长度的数值 a[i]， a[i]表示从i向终点方向跳跃的 最大长度。

换句话说，如果小明在i位置，那么小明能够跳跃的区间就是 i~i+a[i],规定小明跳的位置都是整数。

小明想知道，它从起点0跳到终点 n-1 的最小跳跃次数是多少。

输入
输入有T组数据（1<=T<=50）。

对于每组数据，输入有两行。

第一行一个整数n；

第二行有n个整数，表示a[i]，（0<=i<=n-1）

输出
输出小明跳到终点的最小跳跃次数。 若小明跳不到终点，输出-1
样例输入 复制
2
5
2 3 1 1 4
4
1 1 1 1
样例输出 复制
2
3

Answer 1

这是一个动态规划问题，可以使用动态规划来解决。

我们可以定义一个数组dp，其中dp[i]表示到达位置i的最小跳跃次数。我们可以从右下角开始遍历，因为右下角是最小的跳跃次数。

对于每个位置i，我们需要考虑两种情况：

1. 如果i+a[i]>=n-1，那么可以直接跳到终点，此时dp[i]=dp[i+a[i]]+1。
2. 如果i+a[i]<n-1，那么我们需要考虑从位置i+a[i]跳跃一次到达终点，此时dp[i]=min(dp[i], dp[i+a[i]]+1)。

最后，我们返回dp[0]即可。

下面是C++代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minJumps(int n, vector<int>& a) {
    vector<int> dp(n, n); // 初始化dp数组为n，表示无法到达的位置
    dp[0] = 0; // 起点不需要跳跃
    for (int i = n - 1; i >= 0; i--) {
        if (i + a[i] >= n - 1) { // 直接跳到终点
            dp[i] = dp[i + a[i]] + 1;
        } else { // 需要从位置i+a[i]跳跃一次到达终点
            dp[i] = min(dp[i], dp[i + a[i]] + 1);
        }
    }
    return dp[0];
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        int res = minJumps(n, a);
        if (res == n) { // 如果无法到达终点，输出-1
            cout << -1 << endl;
        } else { // 否则输出最小跳跃次数
            cout << res << endl;
        }
    }
    return 0;
}