时间戳

首页 > 解决方案 > 动态编程实现错误

algorithm - 动态编程实现错误

问题描述

所以我正在参加 atcoder 的教育 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 之前发生的最小可能总成本。

我的尝试

所以我使用了动态编程，这是我的代码

// 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。有人可以指出我的算法有什么问题。我似乎无法理解它。

标签： algorithmc++11

解决方案

问题是当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]它仍然足够大，可以被认为是无限大。

推荐阅读