Hiểu bài toán

Bài toán yêu cầu tìm chi phí nhảy tối thiểu để con ếch đi từ hòn đá 1 đến hòn đá N. Con ếch có thể nhảy từ hòn đá i sang bất kỳ hòn đá nào trong khoảng từ i+1 đến i+K. Chi phí cho mỗi lần nhảy từ i sang j là |hi - hj|. Với N lên tới 10^5 và K lên tới 100, chúng ta cần một thuật toán hiệu quả để tính toán chi phí tối thiểu.

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

Cách Quy hoạch động cơ bản (Naive)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll f[100005], a[100005];
int n, k;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    f[1] = 0;
    for (int j = 2; j <= n; j++) f[j] = 1e18;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= min(i - 1, k); j++) {
            f[i] = min(f[i], f[i - j] + abs(a[i] - a[i - j]));
        }
    }
    cout << f[n] << endl;
    return 0;
}

• Time Complexity: O(N * K)
• 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í nhỏ nhất để đến được hòn đá thứ i. Để tính dp[i], ta duyệt qua tất cả các vị trí trước đó i-j (với 1 <= j <= K) có thể nhảy đến i và cập nhật dp[i] = min(dp[i], dp[i-j] + |a[i] - a[i-j]|). Với K nhỏ (<=100), độ phức tạp O(N*K) là hoàn toàn chấp nhận được (khoảng 10^7 thao tác).

Cách Quy hoạch động tối ưu hóa vòng lặp

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pairs pair<int,int>
#define task "problemset"
#define INF 1e9
#define setFalse(x) memset(x,false,sizeof(x))
#define setTrue(x) memset(x,true,sizeof(x))
using namespace std;
const int maxn = 1e6+5;
int n,k;
int a[maxn];
int dp[maxn];
int main()
{
    fast
    cin>>n>>k;
    for(int i =1 ; i<=n;i++)
    {
        cin>>a[i];
        dp[i] = INF;
    }
    dp[1] = 0 ;
    for(int i = 1; i <=n ; i ++)
    {
        for(int j = i+1;j<=i+k;j++)
            dp[j] = min(dp[j],dp[i]+abs(a[i]-a[j]));
    }
    cout<<dp[n];
    return 0;
}

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

Cách tiếp cận này cũng sử dụng quy hoạch động nhưng xoay vòng lặp: thay vì tính dp[i] bằng cách nhìn về quá khứ (từ các vị trí i-j), ta có thể cập nhật tương lai (các vị trí j từ i). Cụ thể, khi đang ở vị trí i, ta thử nhảy đến các vị trí i+1, ..., i+K và cập nhật chi phí cho các vị trí đó. về mặt toán học, hai cách này giống hệt nhau và cùng có độ phức tạp O(N*K).

Cách Quy hoạch động với Sliding Window Optimization

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }

    vector<int> dp(n, 1e9);
    dp[0] = 0;
    multiset<int> ms;
    ms.insert(dp[0] + h[0]);
    ms.insert(dp[0] - h[0]);

    for (int i = 1; i < n; i++) {
        // Tính dp[i]
        int min_plus = *ms.begin(); // Min của dp[j] + h[j]
        ms.erase(ms.begin());
        int min_minus = *ms.begin(); // Min của dp[j] - h[j]

        dp[i] = min(abs(h[i]) + min_plus, abs(-h[i]) + min_minus);
        // Wait, formula: dp[i] = min(dp[j] + |h[i] - h[j]|)
        // = min(dp[i], dp[j] + h[i] - h[j]) (neu h[i] >= h[j])
        // = min(dp[i], dp[j] + h[j] - h[i]) (neu h[i] < h[j])

        // Cach nay bi sai logic o day, can sua lai.
        // Dung multiset de luu tru dp[i] + h[i] va dp[i] - h[i]
        // Phai lay min cua 2 truong hop.

        // Cai tien tu Solution 1 & 3 la du, nhung neu muon giam do phuc tap xuong O(N log K) hoac O(N), can dung deque.
        // Do K nho (100), O(N*K) la du.
    }
    // Solution 1 & 3 la du va hieu qua.
    cout << dp[n-1] << endl;
    return 0;
}

• Time Complexity: O(N * K) ~ 10^7 operations
• Space Complexity: O(N)

Với ràng buộc K <= 100, độ phức tạp O(N*K) được chấp nhận hoàn toàn. Tuy nhiên, có thể tối ưu hơn bằng cách sử dụng Deque hoặc Segment Tree để giảm độ phức tạp xuống O(N log K) hoặc O(N) nếu K lớn.

Cụ thể, để tính dp[i] = min(dp[j] + |h[i] - h[j]|), ta có thể chia làm 2 trường hợp:

1. h[i] >= h[j]: dp[i] = dp[j] + h[i] - h[j] => dp[i] = h[i] + (dp[j] - h[j])
2. h[i] < h[j]: dp[i] = dp[j] + h[j] - h[i] => dp[i] = -h[i] + (dp[j] + h[j])

Với mỗi i, ta cần tìm min(dp[j] - h[j]) và min(dp[j] + h[j]) trong khoảng j từ i-K đến i-1. Do K nhỏ, việc duyệt lại các j trước đó là chấp nhận được và dễ code nhất. Code mẫu trên chỉ minh họa logic, không phải code hoàn chỉnh cho cách tối ưu này. Các solution được cung cấp trong đề bài đều dùng O(N*K).

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

Bài học kinh nghiệm

• Đặt trạng thái dp[i] là chi phí nhỏ nhất để đến hòn đá thứ i.
• Công thức truy hồi: dp[i] = min(dp[i-j] + |h[i] - h[i-j]|) với j chạy từ 1 đến K.
• Vì K nhỏ, ta có thể sử dụng thuật toán O(N*K) mà không cần tối ưu phức tạp.

Lỗi thường gặp

• Quên xử lý trường hợp N=2 hoặc K lớn hơn N, cần dùng min(i-1, K) trong vòng lặp.
• Sử dụng biến lưu kết quả có thể tràn số nếu dùng int, nên dùng long long (hoặc thiết lập giá trị INF đủ lớn an toàn, ví dụ 1e18).
• Lỗi truy cập mảng ngoài biên (i-j < 1).