Skip to main content
Computer Science

Return to Answer

fix sentence missing a word
Source Link
jnalanko
jnalanko
  • 587
  • 5
  • 10

Here is another slightly different way of phrasing what dynamic programming gives you. Dynamic programming collapses an exponential number of candidate solutions into a polynomial number of equivalence classes, such that the candidate solutions in each class are indistinguishable in some sense.

Let me take as an example the problem of finding the number of increasing subsequences of length $k$ in an array $A$ of lenght $n$. It is useful to partition the set of all subsequences into equivalence classes such that two subsequences belong to the same class if and only if they have the same length and end in the same index. All of the $2^n$ possible subsequences belong to exactly one of the $O(n^2)$ equivalence classes. This partitioning preserves enough information so that we can define a recurrence relation for the sizes of the classes. If $f(i, \ell)$ gives the number of subsequences which end in index $i$ and have length $\ell$, then we have:

$$f(i,\ell) = \sum_{j < i \textrm{ such that} A[j] < A[i]} f(j,\ell-1)$$ $$f(i,1) = 1 \textrm{ for all } i = 1 \ldots n$$

This recurrence solves the problem in time $O(n^2k)$.

Here is another slightly different way of phrasing what dynamic programming gives you. Dynamic programming collapses an exponential number of candidate solutions into a polynomial number of equivalence classes, such the candidate solutions in each class are indistinguishable in some sense.

Let me take as an example the problem of finding the number of increasing subsequences of length $k$ in an array $A$ of lenght $n$. It is useful to partition the set of all subsequences into equivalence classes such that two subsequences belong to the same class if and only if they have the same length and end in the same index. All of the $2^n$ possible subsequences belong to exactly one of the $O(n^2)$ equivalence classes. This partitioning preserves enough information so that we can define a recurrence relation for the sizes of the classes. If $f(i, \ell)$ gives the number of subsequences which end in index $i$ and have length $\ell$, then we have:

$$f(i,\ell) = \sum_{j < i \textrm{ such that} A[j] < A[i]} f(j,\ell-1)$$ $$f(i,1) = 1 \textrm{ for all } i = 1 \ldots n$$

This recurrence solves the problem in time $O(n^2k)$.

Here is another slightly different way of phrasing what dynamic programming gives you. Dynamic programming collapses an exponential number of candidate solutions into a polynomial number of equivalence classes, such that the candidate solutions in each class are indistinguishable in some sense.

Let me take as an example the problem of finding the number of increasing subsequences of length $k$ in an array $A$ of lenght $n$. It is useful to partition the set of all subsequences into equivalence classes such that two subsequences belong to the same class if and only if they have the same length and end in the same index. All of the $2^n$ possible subsequences belong to exactly one of the $O(n^2)$ equivalence classes. This partitioning preserves enough information so that we can define a recurrence relation for the sizes of the classes. If $f(i, \ell)$ gives the number of subsequences which end in index $i$ and have length $\ell$, then we have:

$$f(i,\ell) = \sum_{j < i \textrm{ such that} A[j] < A[i]} f(j,\ell-1)$$ $$f(i,1) = 1 \textrm{ for all } i = 1 \ldots n$$

This recurrence solves the problem in time $O(n^2k)$.

Source Link
jnalanko
jnalanko
  • 587
  • 5
  • 10

Here is another slightly different way of phrasing what dynamic programming gives you. Dynamic programming collapses an exponential number of candidate solutions into a polynomial number of equivalence classes, such the candidate solutions in each class are indistinguishable in some sense.

Let me take as an example the problem of finding the number of increasing subsequences of length $k$ in an array $A$ of lenght $n$. It is useful to partition the set of all subsequences into equivalence classes such that two subsequences belong to the same class if and only if they have the same length and end in the same index. All of the $2^n$ possible subsequences belong to exactly one of the $O(n^2)$ equivalence classes. This partitioning preserves enough information so that we can define a recurrence relation for the sizes of the classes. If $f(i, \ell)$ gives the number of subsequences which end in index $i$ and have length $\ell$, then we have:

$$f(i,\ell) = \sum_{j < i \textrm{ such that} A[j] < A[i]} f(j,\ell-1)$$ $$f(i,1) = 1 \textrm{ for all } i = 1 \ldots n$$

This recurrence solves the problem in time $O(n^2k)$.