Friedforks's blog

AT: Frog 1

Starter

比较简单，不多说。有两种DP方式：pull dp，push dp，代码中解释区别。但是本质上是一样的。

/*
 * Created by: Chixiyu
 * Date: 2025-02-12
 */
#include <bits/stdc++.h>
#include <climits>
#include <cstdlib>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    // dp[i] is the minimum cost to reach stone i
    vector<int> dp(n, INT_MAX);
    vector<int> h(n);
    for (auto &it : h)
        cin >> it;
    // init state
    dp[0] = 0; // start with 0 cost

    // solution 1. push dp: computing future based on current
    //
    // for (int i = 0; i < n - 1; i++) {
    //     // jump one step
    //     dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i + 1] - h[i]));
    //     // jump two step
    //     if (i + 2 < n) {
    //         dp[i + 2] = min(dp[i + 2], dp[i] + abs(h[i + 2] - h[i]));
    //     }
    // }
    //
    //
    // solution 2. pull dp: computing current based on past
    for (int i = 1; i < n; i++) {
        // jump one step
        dp[i] = min(dp[i], dp[i - 1] + abs(h[i - 1] - h[i]));
        // jump two step
        if (i - 2 >= 0) {
            dp[i] = min(dp[i], dp[i - 2] + abs(h[i - 2] - h[i]));
        }
    }
    cout << dp[n - 1] << endl;
    return 0;
}

AT: Frog 1

AT: Frog 1

评论