Dynamic Programming

Let $A$ be an array containing integer values. The distance of $A$ is defined as the minimum number of elements in $A$ that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. The distance of the array [2, 5, 3, 1, 4, 2, 6] is __________

Consider the weights and values of items listed below. Note that there is only one unit of each item. $$\begin{array}{|c|c|c|} \hline \textbf{Item number} & \textbf{Weight (in Kgs)} & \textbf{Value (in Rupees)} \\ \hline 1 & 10 & 60 \\ \hline 2 & 7 & 28 \\ \hline 3 & 4 & 20 \\ \hline 4 & 2 & 24 \\ \hline \end{array}$$ The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by $V_{\text{opt}}$. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by $V_{\text{greedy}}$. The value of $V_{\text{opt}} - V_{\text{greedy}}$ is _____.

Let $A_1$, $A_2$, $A_3$, and $A_4$ be four matrices of dimensions $10 \times 5$, $5 \times 20$, $20 \times 10$, and $10 \times 5$, respectively. The minimum number of scalar multiplications required to find the product $A_1A_2A_3A_4$ using the basic matrix multiplication method is ________.

Consider two strings $A$ = "qpqrr" and $B$ = "pqprqrp". Let $x$ be the length of the longest common subsequence (not necessarily contiguous) between $A$ and $B$ and let $y$ be the number of such longest common subsequences between $A$ and $B$. Then $x + 10y$ = _____.

Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers $i, j$ with $i < j$. Given a shortcut $i, j$ if you are at position $i$ on the number line, you may directly move to $j$. Suppose $T(k)$ denotes the smallest number of steps needed to move from $k$ to 100. Suppose further that there is at most 1 shortcut involving any number, and in particular from 9 there is a shortcut to 15. Let $y$ and $z$ be such that $T(9) = 1 + \min(T(y), T(z))$. Then the value of the product $yz$ is _____.