vendredi 24 avril 2020

Dynamic Programming Implementation Bug

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