129 views
2 2 votes

True or False:

In every dynamic-programming solution, the asymptotic space requirement must be at least as large as the total number of distinct subproblems.

  1. True
     
  2. False

1 Answer

0 0 votes

Dynamic programming may have many distinct subproblems, but we do not necessarily need to keep all their answers simultaneously.

Consider Edit Distance for two strings of length approximately $n$.

The usual DP table contains $n\times n$ states.

So the number of distinct subproblems is $\Theta(n^2)$

However, when computing one row of the table, we often need only the immediately preceding row.

Therefore, instead of storing the full table, we can keep:

  • Previous row
  • Current row

Each row has $\Theta(n)$ entries.

Thus, the space requirement can be reduced to $\Theta(n)$ even though the number of subproblems remains $\Theta(n^2)$

$\therefore \text{Space} < \text{Number of subproblems}$ is entirely possible.

Hence,

$\boxed{\text{Answer: (B) False}}$

Answer:
Position:
Show:

Related questions

1 1 vote
1 1 answer
85
85 views
GO Classes asked Aug 22
85 views
There is an unlimited supply of three item types:$$\begin{array}{|c|cc|}\hline\text{Item} & \text{Size} & \text{Value} \\\hlineA & 1 & 2 \\B & 2 & 6 \\C & 3 & 9 \\\hline\...
0 0 votes
1 1 answer
83
83 views
GO Classes asked Aug 22
83 views
The following function $\texttt{CalcEditDistance}$ computes the edit distance between two strings.For this problem:Inserting one character has cost $1$.Deleting one chara...
2 2 votes
1 1 answer
89
89 views
0 0 votes
1 1 answer
72
72 views
GO Classes asked Aug 22
72 views
An instance of Subset Sum contains:$n$ positive integersa positive target value $m$What is the running time of the standard dynamic-programming solution?$\Theta(m+n)$ $\T...