1
$\begingroup$

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 $ )

Improve this question
$\endgroup$
1
  • $\begingroup$ 2a. Because nothing requires $k$ to be 0. And if it's not 0, then there is no value of $j$ for which the RHS equals the LHS, so they are not "of the same form". $\endgroup$
    – j_random_hacker
    Commented Sep 4, 2021 at 2:23

1 Answer 1

Reset to default
2
$\begingroup$

The essence of dynamic programming is "it is easier to solve many problems than to solve one problem.". Sometimes, the more problems the easier. Sometimes, it is impossible with less problems.

The approach of dynamic programming is finding/inventing many problems that are similar to each other, solving these similar problems in some order so that we can obtain the solution to the original problem.

There is no mathematical definition for "subproblems".

As I understand it in the context of dynamic programming, they just mean the many problems we hope to/should/will find, through the solution to which the solution to the original problem can be obtained. Most of the time, it is immediate to tell if an approach is dynamic programming, as we would deduce/build/find mathematical recurrence relation among the solutions to those "subproblems", which will be used in the code.

It is, in fact, not very accurate to call those similar problems "subproblems" in the sense that those similar problems

  • might be larger than the original problem in the sense of input size or the number of input parameters
  • might be larger than the original problem in the sense of output size or the number of output parameters
  • might not include the original problem as a special case, or might include the original problem as a special case.

We call those similar problems "subproblems" for some reasons:

  • those similar problems are used to solve the original problem,
  • those similar problems are similar to the original problem, usually, although not as similar as among themselves,
  • those similar problems often include the versions of the original problem with smaller input.
  • "subproblems", as a word, is short.

"Why are the subproblem $ A_{k+1} A_{k+2} \cdots A_j $ not of the form $ A_1 A_2 \cdots A_j $?"

Sure, the former are of the latter form if you consider that subscript "${}_1$" in "$A_1$" means a placeholder for an arbitrary starting index. There is nothing wrong with that.

However, you are supposed to understand (or you are supposed to find the understanding) that "$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. 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 $", sine two numbers are needed to specify them.

You might have overlooked the extremely obvious simple fact that the number of numbers/values that are needed to specify the input of a particular subproblem is critical. Or the number of input parameters of a function/methods/procedure/problem is critical. You just have to make a clear-cut choice on that number. If one parameter is enough, use one. It one parameter is not enough but two parameter is enough, use two.

In the current case of optimal parenthesization of the matrix-chain multiplication, the "many problems" that we could/should find/invent are the optimal parenthesization of some contiguous elements in the given matrix chain where both ends must vary. If we only allow one end to vary, then we will not have enough subproblems to solve the original problem, in the sense that those subproblems are not similar/close/related enough to each other for us to solve enough more subproblems based on the subproblems that we have solved.

For more explanation, read the CLRS book.
Fore more refined and clearer explanation, reach the CLRS book.
(When you do not understand some pieces in that book immediately, continue reading. And read again.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.