动态编程实现错误

Question

所以我正在atcoder的教育DP竞赛中练习DP，我被困在第一个问题上。

问题陈述

有N块石头，编号为1,2，…，N。对于每个i(1≤i≤N(，石头i的高度为)，石头的高度h[i]。有一只青蛙最初在石头上1.它将重复以下动作若干次以到达Stone N:

如果青蛙当前在石头i上，跳到石头i+1或石头i+2。这里，产生了|h[i]-h[j]|的成本，其中j是要降落的石头找出青蛙到达Stone之前可能产生的最小总成本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。有人能指出我的算法出了什么问题吗。我似乎无法理解。

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]使用较小的初始值，该初始值仍然足够大，可以被认为是无限大。

Answer 2

int dp[N + 1];
dp[N] = INT_MAX;

将其制成：

int dp[N+1]={INT_MAX};