Frog 1
لديك مصفوفة \(h\) تحتوي على \(N\) عنصرًا.أنت تبدأ من العنصر الأول ويجب أن تصل إلى العنصر الأخير باستخدام الحركات التالية:
- التحرك من الموقع \(i\) إلى \(i + 1\) بتكلفة \(|h_i - h_{i + 1}|\).
- التحرك من الموقع \(i\) إلى \(i + 2\) بتكلفة \(|h_i - h_{i + 2}|\).
جد أقل تكلفة للتحرك من العنصر الأول إلى العنصر الأخير.
في هذه المشكلة سنفترض أن كل شيء يبدأ من الصفر. أي أن جميع مواقع المصفوفة تبدأ من \(0\).
Solution
سنقوم بحل هذه المشكلة باستخدام البرمجة الديناميكية.
أولاً، سنعرف الحالة \(f(i)\) لتكون أقل تكلفة للوصول إلى الموقع \(i\) بدءًا من الموقع \(0\).
بعد ذلك، سنعرف الانتقال. هناك طريقتان للوصول إلى الموقع \(i\): من \(i - 1\) أو من \(i - 2\).
إذا وصلنا إلى الموقع \(i\) من \(i-1\)، فإن \(f(i)\) هو أقل تكلفة للوصول إلى \(i-1\) من \(0\) بالإضافة إلى تكلفة الانتقال من \(i-1\) إلى \(i\).
\(f(i) = f(i - 1) + |h_{i - 1} - h_i|\)
إذا وصلنا إلى الموقع \(i\) من \(i-2\)، فإن \(f(i)\) هو أقل تكلفة للوصول إلى \(i-2\) من \(0\) بالإضافة إلى تكلفة الانتقال من \(i-2\) إلى \(i\).
\(f(i) = f(i - 2) + |h_{i - 2} - h_i|\)
بما أننا لا نعرف أي الخيارين هو الأمثل، فسنأخذ الأدنى بين كلا الخيارين .
\(f(i) = min(f(i - 1) + |h_{i - 1} - h_i| , f(i - 2) + |h_{i - 2} - h_i|)\)
الحالة الأساسية لدينا ستكون:
\(f(0) = 0\)
\(f(1) = |h_0 - h_1|\)
المساحة في الخوارزمية يحدده عدد الحالات، وهو \(O(N)\).
الزمن هو عدد الحالات \(N\) مضروبًا في التعقيد الزمني لكل انتقال \(O(1)\)، لذا يكون التعقيد الكلي \(O(N)\).
#include <iostream>
using namespace std;
int a[200000];
int dp[200000];
int f(int i) {
// الحالات الأساسية
if (i == 0) {
return 0;
}
if (i == 1) {
return abs(a[1] - a[0]);
}
// إذا تم حساب الحل من قبل
if (dp[i] != -1) {
return dp[i];
}
dp[i] = min(
f(i - 1) + abs(a[i] - a[i - 1]),
f(i - 2) + abs(a[i] - a[i - 2])
);
return dp[i];
}
int main() {
// أسند 1- لجميع العناصر للإشارة إلى أننا لا نعرف حل أي حالة
for (int i = 0; i < 200000; i++) {
dp[i] = -1;
}
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
cout << f(n - 1) << "\n";
}