The matrix-chain multiplication for a chain of matrices\

A_(1)dotsA_(n)

\ is an example of a dynamic programming problem. Consider the subchain\

A_(i)A_(i+1)dotsA_(j)

.\ Recall that the problem is to minimize the cost of the multiplication (in terms of the number of required scalar multiplications) by choosing where to parenthesize the chain. In this case, choosing where to split the chain and parenthesizing terms results in (a) how many subproblems and (b) how many choices for the split?\ 2 subproblems, j-i choices\ 1 subproblem, n-j choices\ 1 subproblem, j choices\ 2 subproblems, n-i choices

The matrix-chain multiplication for a chain of matrices A1An is an example of a dynamic programming problem. Consider the subchain AiAi+1Aj Recall that the problem is to minimize the cost of the multiplication (in terms of the number of required scalar multiplications) by choosing where to parenthesize the chain. In this case, choosing where to split the chain and parenthesizing terms results in (a) how many subproblems and (b) how many choices for the split? 2 subproblems, j-i choices 1 subproblem, n-j choices 1 subproblem, j choices 2 subproblems, ni choices