アルゴリズム - 動的プログラミング

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]は、要素の最大数はrange [1, i]で、Cのこの値を得るために、変更する必要はありません、と私たちはa[i]を変更しないでください表します。

その後|a[i] - a[j]| <= (j - i) * Cは、我々は