Algorithmen - Dynamische Programmierung - Arrays, Algorithmus, dynamische Programmierung

Gegeben ein Array von n Elementen a1, a2 ... an. Definieren wir eine Funktion C = max | a (i + 1) -a (i) | für i = 2 bis n-1. Also können wir einen Wert von C für unser Array berechnen. Jetzt ist das Problem, wenn wir das Array und einen gewissen Wert von C erhalten, wie viele Elemente im Array geändert werden sollten, um diesen Wert von C zu erhalten?

Dies ist ein Teil der Lösung dieses Codeforce-Problems: http://codeforces.com/contest/361/problem/D

Es wird mit dynamischer Programmierung gelöst, aber ich verstehe die Antwort nicht. Könnte mir jemand das erklären? Hier ist der Code.

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

Antworten:

In diesem Code dp[i] bezeichnet die maximale Anzahl von Elementen, die nicht geändert werden müssen, um diesen Wert von C zu erhalten, in range [1, i]und wir ändern uns nicht a[i].

Dann überprüfe jeden j > i, ob |a[i] - a[j]| <= (j - i) * CWir müssen alle Elemente zwischen i und j ändern dp[j] = max(dp[j], dp[i] + 1)