Practice - 5 Tasks
Answer the questions below
1fill in blank
easyComplete the code to initialize the dp table with zeros.
DSA Java
int n = dims.length - 1; int[][] dp = new int[n][n]; for (int i = 0; i < n; i++) { dp[i][i] = [1]; }
Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Setting dp[i][i] to 1 or -1 instead of 0.
Using Integer.MAX_VALUE which is for initialization of minimum cost.
✗ Incorrect
The diagonal elements represent single matrices, so their multiplication cost is zero.
2fill in blank
mediumComplete the code to calculate the cost of multiplying two matrices.
DSA Java
int cost = dims[i] * dims[k + 1] * [1];
Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Using dims[j] or dims[i+1] instead of dims[j+1].
Confusing the indices for matrix dimensions.
✗ Incorrect
The cost formula uses dims[i] * dims[k+1] * dims[j+1], where dims[j+1] is the number of columns of the second matrix.
3fill in blank
hardFix the error in the loop condition to correctly iterate over chain lengths.
DSA Java
for (int length = 2; length <= [1]; length++) { // code }
Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Using dims.length which is one more than number of matrices.
Using n - 1 which is too small.
✗ Incorrect
The chain length goes from 2 to n, where n is the number of matrices.
4fill in blank
hardFill both blanks to correctly update the dp table with minimum multiplication cost.
DSA Java
for (int i = 0; i < n - length + 1; i++) { int j = i + length - 1; dp[i][j] = [1]; for (int k = i; k < j; k++) { int cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]; if (cost < dp[i][j]) { dp[i][j] = [2]; } } }
Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Initializing dp[i][j] with 0 which causes incorrect minimum calculation.
Assigning dp[i][j] to dp[i][k] instead of cost.
✗ Incorrect
Initialize dp[i][j] with a very large value and update it with the minimum cost found.
5fill in blank
hardFill all three blanks to complete the recursive memoization function for matrix chain multiplication.
DSA Java
public int matrixChainMemo(int[] dims, int i, int j, int[][] dp) {
if (i == j) return [1];
if (dp[i][j] != [2]) return dp[i][j];
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int cost = matrixChainMemo(dims, i, k, dp) + matrixChainMemo(dims, k + 1, j, dp) + dims[i] * dims[k + 1] * dims[j + 1];
if (cost < dp[i][j]) dp[i][j] = [3];
}
return dp[i][j];
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Returning 1 instead of 0 in base case.
Checking dp[i][j] against 0 instead of -1.
Assigning dp[i][j] to Integer.MAX_VALUE instead of cost.
✗ Incorrect
Base case returns 0 cost; dp initialized with -1 to mark uncomputed; update dp[i][j] with cost if smaller.