Độ phức tạp thời gian: ~O(N)~

Để giải quyết bài này ta sẽ dùng quy hoạch động. Ta định nghĩa ~dp[i]~ là chi phí ít nhất để đến được hòn đá thứ ~i~. Dễ thấy để đến được hòn đá thứ ~i~, ta chỉ có thể nhảy từ :

• Hòn đá thứ ~i - 1~ với ~( 1 < i \le N)~.
• hòn đá thứ ~i - 2~ với ~( 2 < i \le N)~.

Vì chú ếch bắt đầu từ hòn đá đầu tiên nên: ~dp[1] = 0~. Từ đây, để đến được hòn đá thứ ~2~ ta có thể nhảy từ hòn đá đầu tiên ~\Rightarrow dp[2] = dp[1] + |h[2] - h[1]|~. Tính trước ~dp[1]~ và ~dp[2]~ ta có:

• ~\forall i, 2 < i \le N , dp[i] = min(dp[i-1] + |h[i] - h[i-1]|, dp[i-2] + |h[i] - h[i-2]|)~

Vì kết thúc ở hòn đá thứ ~N~ nên kết quả bài toán là ~dp[N]~.

Hướng dẫn cài đặt:

#include <iostream>
using namespace std;
const long long N = 2e5 + 5;
int dp[N], h[N], n;

int main(){
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> h[i];

    dp[1] = 0; dp[2] = abs(h[1] - h[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;
}