Advertisement
Josif_tepe

Untitled

Apr 6th, 2022
1,236
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <math.h>
  5. #include <vector>
  6. #include <queue>
  7. using namespace std;
  8. int n;
  9. int arr[100005];
  10. int dp[100005];
  11. int frog(int i) {
  12.     if(i >= n - 1) {
  13.         return 0;
  14.     }
  15.     if(dp[i] != -1) {
  16.         return dp[i];
  17.     }
  18.     int result = 2e9;
  19.     if(i + 1 < n)
  20.         result = min(result, frog(i + 1) + abs(arr[i + 1] - arr[i]));
  21.     if(i + 2 < n)
  22.         result = min(result, frog(i + 2) + abs(arr[i + 2] - arr[i]));
  23.    
  24.     return dp[i] = result;
  25. }
  26. int main()
  27. {
  28.     cin >> n;
  29.     for(int i = 0; i < n; i++) {
  30.         cin >> arr[i];
  31.     }
  32.     memset(dp, -1, sizeof dp);
  33.     cout << frog(0) << endl;
  34.     return 0;
  35. }
  36.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement