Dynami c Ошибка реализации программирования

Question

Итак, я работаю над образовательным конкурсом аткодеров DP для практики с DP, и я застрял на первом вопросе.

Постановка задачи

Есть N камней, пронумерованы 1,2,…, N. Для каждого i (1 ≤ i≤ N) высота Камня i), высота Камня h [i]. Есть лягушка, которая изначально находится на Камне 1. Она будет повторять следующее действие несколько раз, чтобы достичь Камня N:

Если лягушка в настоящее время находится на камне i, прыгните на камень i + 1 или Камень i + 2. Здесь стоимость | h [i] - h [j] | происходит, где j - камень для приземления. Найдите минимально возможную общую стоимость, понесенную до того, как лягушка достигнет Камня N.

Моя попытка

Итак, я использовал динамический c программирование и это мой код

// 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];
}

Когда я проверяю свой алгоритм на этом тестовом примере,

4
10 30 40 20

Я продолжаю получать неправильный ответ -2147483599, а иногда 50 , Может кто-то указать, что не так с моим алгоритмом. Кажется, я не могу обойти это.

Answer 1

Проблема в том, что при выполнении abs(cost[i] - cost[i + 2]) + dp[i + 2] на первом шаге, поскольку dp[i + 1] равно INT_MAX, тип int переполняет и создает отрицательное значение, которое затем используется для неправильного обновления в dp.

Одним из возможных решений является использование long long dp[N + 1] вместо int dp[N + 1]. Другое - использовать меньшее начальное значение для dp[N], которое все равно будет достаточно большим, чтобы считаться бесконечно большим.