Hiểu bài toán

Bài toán yêu cầu tìm chi phí nhảy tối thiểu để một con ếch đi từ hòn đá 1 đến hòn đá N. Con ếch có thể nhảy từ hòn đá i sang hòn đá i+1 hoặc i+2 với chi phí là độ chênh lệch chiều cao绝对值 giữa hai hòn đá đó. Nhiệm vụ là tính tổng chi phí nhỏ nhất cho hành trình này.

Các cách tiếp cận

Cách Quy hoạch động cơ bản (Duyệt tiến)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> h(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> h[i];
    }

    vector<long long> dp(N + 1, 1e18);
    dp[1] = 0;

    // Duyệt từ hòn đá 1 đến N
    for (int i = 1; i < N; i++) {
        // Nhảy sang i+1
        if (i + 1 <= N) {
            dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]));
        }
        // Nhảy sang i+2
        if (i + 2 <= N) {
            dp[i + 2] = min(dp[i + 2], dp[i] + abs(h[i] - h[i + 2]));
        }
    }

    cout << dp[N];
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là cách tiếp cận trực tiếp nhất. Ta định nghĩa dp[i] là chi phí tối thiểu để đến được hòn đá thứ i. Khởi tạo dp[1] = 0. Sau đó, duyệt qua từng hòn đá i từ 1 đến N-1, và cập nhật chi phí cho các hòn đá có thể nhảy tới (i+1 và i+2). Công thức cập nhật: dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j])). Cuối cùng, dp[N] là đáp án.

Cách Quy hoạch động tối ưu (Duyệt tiến từ đầu)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<ll> f(n + 1, 1e18);
    f[1] = 0;
    if (n >= 2) f[2] = abs(a[2] - a[1]); // Có thể thêm bước khởi tạo này cho rõ ràng

    // Hoặc có thể bắt đầu vòng lặp từ 1
    for (int i = 1; i < n; i++) {
        if (i + 1 <= n) f[i + 1] = min(f[i + 1], f[i] + abs(a[i] - a[i + 1]));
        if (i + 2 <= n) f[i + 2] = min(f[i + 2], f[i] + abs(a[i] - a[i + 2]));
    }

    cout << f[n] << endl;
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Cách này về cơ bản giống cách 1 nhưng được tối ưu hóa một chút về mặt code structure. Thay vì duyệt tất cả các j từ i+1 đến i+2, ta trực tiếp cập nhật các trường hợp nhảy. Mảng dp (ở đây là f) lưu chi phí tối thiểu để đến từng vị trí. Vòng lặp chạy từ 1 đến N-1, đảm bảo rằng khi xét vị trí i, dp[i] đã có giá trị tối ưu.

Cách Quy hoạch động (Công thức truy hồi)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> h(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> h[i];
    }

    vector<ll> dp(N + 1, 1e18);
    dp[1] = 0;
    // Nếu N >= 2, ta có thể nhảy thẳng từ 1 sang 2
    if (N >= 2) dp[2] = abs(h[2] - h[1]);

    // Duyệt từ 3 đến N để tính dp[i] dựa trên dp[i-1] và dp[i-2]
    for (int i = 3; i <= N; i++) {
        dp[i] = min(
            dp[i - 1] + abs(h[i] - h[i - 1]),
            dp[i - 2] + abs(h[i] - h[i - 2])
        );
    }

    cout << dp[N];
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là cách suy nghĩ khác về quy hoạch động. Thay vì nghĩ 'từ i ta có thể đi đâu', ta nghĩ 'để đến i, ta phải đến từ đâu'. Để đến hòn đá i, con ếch chỉ có thể nhảy từ i-1 hoặc i-2. Do đó, dp[i] = min(dp[i-1] + cost(i-1 -> i), dp[i-2] + cost(i-2 -> i)). Cách này thường dễ code hơn và có cấu trúc rõ ràng. Ta khởi tạo dp[1] = 0, dp[2] = cost(1->2) rồi lặp từ 3 đến N.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có tính chất optimal substructure (cấu trúc tối ưu) và overlapping subproblems (các bài toán con trùng lặp), phù hợp với Quy hoạch động (Dynamic Programming).
• Chi phí để đến hòn đá i chỉ phụ thuộc vào chi phí của 2 hòn đá trước đó (i-1 và i-2).
• Có thể trình bày DP theo 2 cách: (1) Duyệt từ đầu và cập nhật các trạng thái tương lai (Forward DP), (2) Duyệt từ đầu và tính dựa trên các trạng thái quá khứ (Backward DP/Recurrence). Cả hai đều hiệu quả O(N).

Lỗi thường gặp

• Lỗi truy cập mảng ngoài biên (off-by-one error): Cần kiểm tra điều kiện i+1 <= N và i+2 <= N khi duyệt tiến, hoặc bắt đầu vòng lặp từ 3 khi duyệt truy hồi.
• Sử dụng biến có kiểu dữ liệu quá nhỏ: Chi phí tổng có thể lên tới khoảng 10^5 * 10^4 = 10^9, nên cần dùng long long (hoặc ll) để tránh tràn số (overflow) nếu dùng int.
• Quên khởi tạo giá trị cho các phần tử của mảng DP: Phải gán giá trị vô cùng lớn (INF) cho tất cả các trạng thái trừ trạng thái ban đầu (dp[1] = 0).