matrix chain multiplication

• Build a 2d array, represent the minimum from i to j. i and j are the split index of the input.
• Distance between i and j must be larger than 1.

• If i == j, the value is 0.(base case)
• dp[i][j] = dp[i] * dp[i-1][j-1] * dp[j].

• dp[i][j] = Math.min(dp[i][j-1] + input[i] * input[j-1] * input[j], dp[i+1][j] + input[i] * input[i+1] * input[j])
• Base case is k == 2, which means the minimum distance of i and j, only two Matrix Multiplication.
• Increase the distance from 3 to n.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public int solution(int[] input) {
  int n = input.length;
  if (n < 3) {
    return 0;
  }
  int[][] dp = new int[n][n];
  for (int i = 0; i < n - 2; i++) {
    dp[i][i + 2] = input[i] * input[i + 1] * input[i + 2];
  }
  for (int k = 3; k < n; k++) {
    for (int i = 0; i < n - k; i++) {
      int j = i + k;
      dp[i][j] = Math.min(dp[i][j - 1] + input[i] * input[j - 1] * input[j], dp[i + 1][j] + input[i] * input[i + 1] * input[j]);
    }
  }
  return dp[0][n - 1];
}

result

Passed the three test case in gfg, but the code is not the same. I’m not sure whether mine is a correct one.