So I am working on atcoder's educational DP contest for practice with DP and I am stuck on the first question.
Problem Statement
There are N stones, numbered 1,2,…,N. For each i (1 ≤ i≤ N), the height of Stone i is ), the height of Stone h[i]. There is a frog who is initially on Stone 1. It will repeat the following action some number of times to reach Stone N:
If the frog is currently on stone i, jump to stone i + 1 or Stone i + 2. Here, a cost of |h[i] - h[j]| is incurred, where j is the stone to land on Find the minimum possible total cost incurred before the frog reaches Stone N.
My Attempt
So I used dynamic programming and this is my code
// cost[i] is the height of stone i
int solve(int cost[], int N) {
int dp[N + 1];
dp[N] = INT_MAX;
dp[N - 1] = 0;
for (int i = N - 2; i >= 0; i--) {
dp[i] = min(abs(cost[i] - cost[i + 1]) + dp[i + 1], abs(cost[i] - cost[i + 2]) + dp[i + 2]);
}
return dp[0];
}
When I test my algorithm on this test case,
4
10 30 40 20
I keep getting the wrong answer -2147483599
and sometimes 50
. Can someone point out what is wrong with my algorithm. I can't seem to get my head around it.
Aucun commentaire:
Enregistrer un commentaire