Problem – https://atcoder.jp/contests/dp/tasks/dp_a
At every instance we have two choices, i.e either jump to ‘i+1’ th or ‘i+2’ th rock, and the cost of jumping for the former is |cost[i] – cost[i+1]| and for the latter it’s |cost[i] – cost[i+2]| and minimum of them is the answer, therefore the recurrence relation would be.
min{f(i+1) + |cost[i] – cost[i+1]| , f(i+2) + |cost[i] – cost[i+2]|}
Here, |x| denotes absolute value of ‘x’
The implementation is rather straight forward.
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define INF 1e9
#define FOR(i,s,e) for(int i=s; i<=e; i++)
int cost[MAXN], memo[MAXN];
int n;
class fastio {
public:
fastio() {
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
}
} __fastio;
int f(int i) {
if(i > n) return INF;
if(i == n) return 0;
if(memo[i] != -1) return memo[i];
return memo[i] = min(f(i+1) + abs(cost[i] - cost[i+1]), f(i+2) + abs(cost[i] - cost[i+2]));
}
void solve() {
cin >> n;
FOR(i,1,n) {
cin >> cost[i];
}
memset(memo, -1, sizeof(memo));
cout << f(1) << endl;
}
int main() {
__fastio;
solve();
return 0;
}
Home of Code 