Recent questions tagged dynamic-programming

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.True False

True or False:The root of an optimal binary search tree must always contain the key having the highest search probability.True False

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...

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\...

The following function $\texttt{CalcEditDistance}$ computes the edit distance between two strings.For this problem:Inserting one character has cost $1$.Deleting one chara...

For an array, $a ,a ,\ldots,a[n]$ consider the proposed DP state:$LIS[i]=$ length of the longest increasing subsequence contained anywhere within $a[1\ldots i]$.Using onl...

A $15$ kg knapsack is given with the following items:$$\begin{array}{|c|cc|}\hline\text{Item} & \text{Weight} & \text{Value} \\\hlineA & 2 & 7 \\B & 3 & 10 \\C & 5 & 18 \...

Consider the sequences:$X=\{A,C,B,C,D,C\}$$Y=\{C,D,B,D,C,A\}$What is the length of their longest common subsequence?

Consider four matrices whose dimension array is:$p=[5,2,2,4,6]$Thus:$A_1:5\times2$$A_2:2\times2$$A_3:2\times4$$A_4:4\times6$Using optimal matrix-chain multiplication, wha...

Consider the following statements.Dynamic programming generally solves smaller subproblems, stores their solutions, and combines those stored results to solve progressive...

Match the LIST-I with LIST-IILIST-ILIST-IIA.Dynamic programmingI.Floyd Warshall Shortest pathB.GreedyII.Huffman codingC.Back trackingIII.Hamiltonian cycle problemD.Branch...

Consider a table $T$, where the elements $T[i][j], 0 \leq i, j \leq n$, represent the cost of the optimal solutions of different subproblems of a problem that is being so...

The longest common subsequence of $\{1,2,3,2,4,1,2\}$ and $\{2,4,3,1,2,1\}$ is$2,1,2,3$$1,3,2,1$$2,3,2,1$$2,3,1,2,1$

When developing a dynamic programming algorithm, the sequence of steps followed is:Construct an optimal solution from computed information.Recursively define the value of...

Arrange the following steps in the correct order to solve the Knapsack problem using Dynamic Programming.Define the base case when the capacity is zero ($0$) or no items ...

Which of the following problems is solved using dynamic programming?Merge sortDepth-first searchBreadth-first searchFibonacci sequence calculation

A subsequence of an array $A$ is any sub-array of $A$, obtained by deleting zero or more elements of $A$ without changing the order of the remaining elements. The input t...