arrays - 算法 - 动态规划

Question

给定一个包含 n 个元素的数组 a1, a2 ... an。如果我们定义一个函数 C = max |a(i+1)-a(i)| 对于 i = 2 到 n-1。所以我们可以为我们的数组计算一个 C 的值。现在的问题是，如果给定数组和 C 的某个值，应该更改数组中的多少个元素才能获得 C 的这个值？

这是此 codeforces 问题解决方案的一部分：http: //codeforces.com/contest/361/problem/D

它是使用动态编程解决的，但我不明白答案。谁能给我解释一下？这是代码。

/* x is the value of the function 
n the size of the array

*/
int Cal(LL x){ 
    for(int i = 1; i <= n; i++)
        dp[i] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            if(abs(a[i] - a[j]) <= 1ll * (j - i) * x) {
                dp[j] = max(dp[j], dp[i] + 1);
            }
        }
    }
    int ret = 0;
    for(int i = 1; i <= n; i++)
        ret = max(ret, dp[i] + 1);
    return n - ret;
}

Answer 1

在此代码中，dp[i]表示不需要更改的最大元素数，以便获得 C 的这个值，在 中range [1, i]，我们不更改a[i]。

然后检查每一个j > i，如果|a[i] - a[j]| <= (j - i) * C我们需要改变 i 和 j 之间的所有元素，那么dp[j] = max(dp[j], dp[i] + 1）