一道简单的动态规划问题。
题目来源：牛客网
链接：https://www.nowcoder.com/questionTerminal/74acf832651e45bd9e059c59bc6e1cbf
一只袋鼠要从河这边跳到河对岸，河很宽，但是河中间打了很多桩子，每隔一米就有一个，每个桩子上都有一个弹簧，袋鼠跳到弹簧上就可以跳的更远。每个弹簧力量不同，用一个数字代表它的力量，如果弹簧力量为5，就代表袋鼠下一跳最多能够跳5米，如果为0，就会陷进去无法继续跳跃。河流一共N米宽，袋鼠初始位置就在第一个弹簧上面，要跳到最后一个弹簧之后就算过河了，给定每个弹簧的力量，求袋鼠最少需要多少跳能够到达对岸。如果无法到达输出-1 。
输入描述:
输入分两行，第一行是数组长度N (1 ≤ N ≤ 10000)，第二行是每一项的值，用空格分隔。
输出描述:
输出最少的跳数，无法到达输出-1
#include <iostream>
#include <cstdint>
#include <vector>
using namespace std;
int MinLeap(const vector<int> &num) {
const int N = num.size();
// 取值范围为 [0, N]，N是从第一个桩子每次只跳一米的次数
vector<int> dp(N + 1, N + 1);
dp[0] = 0;
// 遍历所有的桩子（最后一个桩子是对岸）
for (int i = 0; i < N + 1; ++i) {
// 从当前桩子向前回溯
for (int j = i - 1; j >= 0; --j) {
// 如果从 j 桩子能够跳到 i 桩子，并且这种跳跃能够减少到 i 桩子的步数
if (j + num[j] >= i && dp[i] > dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
}
if (dp[N] == N + 1) {
return -1;
}
else {
return dp[N];
}
}
int main () {
int N = 0;
cin >> N;
vector<int> num(N, 0);
for (int i = 0; i < N; ++i) {
cin >> num[i];
}
cout << MinLeap(num) << endl;
return 0;
}