袋鼠过河题解(动态规化+贪心算法)

#include <iostream>
#include <vector>
#include <climits>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    vector<int> arr(n + 2, n + 1); //桩子
    vector<int> ans(n + 2, INT_MAX); // 到达每个桩子的最少步数
    ans[n + 1] = -1;
    ans[0] = 0;
    ans[1] = 0;
    for (int i = 1; i <= n; ++ i) {
        cin >> arr[i]; // 输入
    }
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= arr[i] && i + j <= n + 1; ++ j) {
            if (ans[i + j] == -1) {
                ans[i + j] = ans[i] + 1;
            } else {
                ans[i + j] = min(ans[i + j], ans[i] + 1);
            }
        }
    }
    cout << (ans[n + 1] < 0 ? -1 : ans[n + 1]) << endl; 
    return 0;
}

#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    vector<int> arr(n, 0);
    for (int i = 0; i < n; ++ i) {
        cin >> arr[i]; // 输入
    }
    int best = 0, jump = 0, cur = 0;
    for (int i = 0; i < n; ++ i) {
        best = max(best, i + arr[i]); // 最远位置
        if (cur == i) { // 如果袋鼠可以跳到当前桩子
            jump ++;
            cur = best;               
        }        
    }
    cout << (cur >= n ? jump : -1);
    return 0;
}