O(n^2) 時間で実行できる Knuth の最適な二分探索木を実装しようとしています。O（n ^ 3）で実行されているコードがあります。
float P[N + 1] = {0, .13, .12, .15, .05, .12, .10, .08, .09, .03, .13};
float sum[N + 1] = {0, .13, .25, .40, .45, .57, .67, .75, .84, .87, 1.00};
float M[N + 1][N + 1];
int root[N + 1][N + 1];
int s, i, j;
float temp;
for (s = 0; s <= N; s++){
for (i = 0; i <= N; i++){
M[s][i] = 0;
root[s][i] = 0;
}
}
for (s = 2; s <= N; s++){
for (i = 1; i <= N - s + 1; i++){
M[s][i] = N;
for (j = i; j <= i + s - 1; j++){
temp = M[j - i][i] + M[i + s - j - 1][j + 1]+ sum[i + s - 1] - sum[i - 1] - P[j];
if (M[s][i] > temp){
M[s][i] = temp;
root[s][i] = j;
}
}
}
}
M はコストの配列です。P は各ノードの確率です。いくつかのアイデアを以下から得ます:動的プログラミング: Knuth による最適な二分探索木 O(n^2) の改良の理由 . 私の場合、3 番目のループを から に変更しようとしfor (j = i; j <= i + s - 1; j++)ましたfor (j = root[s+1][i]; j <= root[s][i-1]; j++)。しかし、うまくいきません。誰かがこの問題について手がかりを教えてもらえますか?