DP: What's a subproblem space? Why have varying indices for a subproblem?

[CGandC]

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, we needed to allow our subproblems to vary at “both ends,” that is, to allow both $i$ and $j$ to
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$ )

 

[pasmith]

I think there is a distinction between "apply this algorithm to the first $k$ elements of this list" and "apply this algorithm to elements $k+1$ to $j$ of this list". The first only requires passing and tracking one index (the right index) but the second requires passing and tracking both left and right indices.

I think you aren't allowed to conflate these by creating a new list consisting only of elements $k+1$ to $j$ of the original list and applying the algorithm to the first $j-k$ elements of this new list. The exact semantics of "create a new list" will vary, and may have costs (in terms of memory and processor cycles) associated with them which are real in computer science but non-existent in abstract mathematics.

 

[CGandC]

So "$A_1 A_2 \cdots A_j$" stands for a contiguous sequence of elements in the matrix chain that start from $A_1$, a fixed element, which implies that it is enough for one number, the value of $j$, to completely specify those elements given the matrix chain?
and in this sense, "$A_{k+1} A_{k+2} \cdots A_j$" is not of the form of "$A_1 A_2 \cdots A_j$", since two numbers are needed to specify them?

 

[Mark44]

So "$A_1 A_2 \cdots A_j$" stands for a contiguous sequence of elements in the matrix chain that start from $A_1$, a fixed element, which implies that it is enough for one number, the value of $j$, to completely specify those elements given the matrix chain?
and in this sense, "$A_{k+1} A_{k+2} \cdots A_j$" is not of the form of "$A_1 A_2 \cdots A_j$", since two numbers are needed to specify them?

Right

 

[CGandC]

Ok, I understand now, thanks for the help!