The short answer is you're creating a 3x3 array (s), and then attempting to access the 5th element in the second row, which obviously doesn't exist.
As the code stands, you're mapping s[1..n-1,2..n]
in the pseudocode to s[0..n-1][0..n-2]
in java, e.g. where the pseudocode says s[1,2]
your java uses s[0][0]
but you're not subtracting the 1 and the 2 in your call to parenterizacao(s,1,n)
You have a mix of indices being mapped to zero-based in some places and not being mapped in others, so you should make it consistent - either use the indices directly as they are in the pseudocode and make the arrays bigger with unused elements (e.g. instead of s[0..2][0..2]
have s[0..3][0..4]
), or make sure you map the indices every time you access the arrays.
Below I've modified your code and kept the original values for i
,j
,k
,l
and n
from the pseudocode but subtracted 1 or 2 as appropriate on each array access:
public static void parenterizacao(int[][] s, int i, int j) {
if (i == j) {
System.out.println("M" + i);
} else {
System.out.println("(");
parenterizacao(s, i, s[i-1][j-2]);
parenterizacao(s, s[i-1][j-2] + 1, j);
System.out.println(")");
}
}
and
for (int i = 1; i <= n; i++) {
m[i-1][i-1] = 0;
}
for (int l = 2; l <= n; l++) {
for (int i = 1; i <= n - l + 1; i++) {
int j = i + l - 1;
m[i-1][j-1] = 9999;
for (int k = i; k <= j - 1; k++) {
int q = m[i-1][k-1] + m[k][j-1] + p[i - 1] * p[k] * p[j];
if (q < m[i-1][j-1]) {
m[i-1][j-1] = q;
s[i-1][j-2] = k;
}
}
}
}
parenterizacao(s, 1, n);
(n
and l
also needed to be switched in the inner loop to match the pseudocode)