# algorithms – Dynamic Programming: What is a subproblem space? Why do we need varying indexes to characterize a subproblem?

In dynamic programming:
1. what is the definition of the space of subproblems? does it have a mathematical definition?

2. why is it necessary to have an arbitrary index for the subproblem to vary?

To elaborate on question 2, I’ve taken the following paragraph from chapter 15.3 in CLRS:

Conversely, suppose that we had tried to constrain our subproblem space for
matrix-chain multiplication to matrix products of the form $$A_1A_2… A_j$$ . As before,
an optimal parenthesization must split this product between $$A_k$$ and $$A_{k+1}$$ for some
$$1 leq k < j$$. Unless we could guarantee that $$k$$ always equals $$j – 1$$, we would find that we had subproblems of the form $$A_1 A_2 … A_k$$ and $$A_{k+1} A_{k+2} … A_j$$, and that the latter subproblem is not of the form $$A_1 A_2 … A_j$$ . For this problem, $$color{red}{text{we needed to allow our subproblems to vary at “both ends,” that is, to allow both } }$$ $$i$$ and $$j$$ to
$$color{red}{text{vary }}$$ in the subproblem $$A_i A_{i+1} … A_j$$ .

2.a. I don’t understand why the subproblem $$A_{k+1} A_{k+2} … A_j$$ is not of the form $$A_1 A_2 … A_j$$ ( $$k+1$$ is considered to be the first index in the problem of finding the optimal parenthization for $$A_{k+1} A_{k+2} … A_j$$ ) whilst $$A_1 A_2 … A_k$$ is considered a correct form ?
2.b. is there some sort of universal instantiation I’m missing in-terms of logic? what do variable indexes have to do with the issue In question 2.a. ?
( I’m think the issue relates to the fact that when we prove a problem has a substructure, we need to prove it for arbitrary indexes, but I’m unable to see the relation between this proof and why $$A_{k+1} A_{k+2} … A_j$$ is not of the form $$A_1 A_2 … A_j$$ if we consider $$k+1$$ as the first index in the subproblem $$A_{k+1} A_{k+2} … A_j$$ )

Posted on Categories Articles