How does dynamic programming work in this example(generating the tables )

Question

For example, a sequence has the defined growth property: if it is a sequence of positive integers $a_{1}, a_{2}, a_{3}....a_{n}$ and such that:

1. $a_{1}=1.$
2. $a_{n+1} \leq$ Max$_{1\leq i \leq n}$ ($a_{i}+1$)

We can quickly compute the number of such sequences of length n with the power of dynamic programing:

Let sequence(l, m) be the number of possible sequences with length l and maximum number in the sequence m. The total number of such sequences for a length can be calculated by summing all the sequences with maximum value ranging from 1 to n for length l. The recurrence can be described as:

sequence(l,m) = sequence(l-1, m-1 ) + m * sequence(l-1,m);

(sequence (l,1)=1, sequence(l,m)=0 if l< m)

As we create a table of size l * m, where we fill the matrix column by column. The base case: the first column of the table sequence(l, 1) = 1 and for the subproblems where l < m the number of sequences will be 0 since the maximum element in sequence can't be bigger than the length of sequence. We can now fill the table in the second column and apply the recurrence relation for every cell and obtain the value fro all combinations of l and m. Finally, We can sum up the last row to calculate the number of sequences.

Understand that the text already gives hint for creating the table. but I am still struggling to visualize it. First of all, What exactly is this sequence?

$a_{2} = a_{1+1} \leq max_{1 \leq i \leq 1}(a_{i}+1) $ which mean i can only be 1. Then $a_{2} \leq max(2)$

and $a_{3}\leq max(3)$ but what are some example of such sequence ? Any more guidance for completing the table?

What is exactly m in sequence(l, m)? Where should we place $a_{4}$ in the table of l * m?

Answer 1

Here are all such sequences of length 1.

[1]

Here are all such sequences of length 2.

[1, 1]
[1, 2]

Here are all such sequences of length 3.

[1, 1, 1]
[1, 1, 2]


[1, 2, 1]
[1, 2, 2]
[1, 2, 3]

Here are all such sequences of length 4.

[1, 1, 1, 1]
[1, 1, 1, 2]


[1, 1, 2, 1]
[1, 1, 2, 2]
[1, 1, 2, 3]

[1, 2, 1, 1]
[1, 2, 1, 2]
[1, 2, 1, 3]

[1, 2, 2, 1]
[1, 2, 2, 2]
[1, 2, 2, 3]


[1, 2, 3, 1]
[1, 2, 3, 2]
[1, 2, 3, 3]
[1, 2, 3, 4]

Please observe how the sequences grow longer and longer with the condition $$a_{n+1} \leq \max_{1\le i \le n} (a_{i}+1) = 1+\max_{1\le i \le n} a_{i}$$ as well as the recurrence relation $$ \text{sequence}(l,m) = \text{sequence}(l-1, m-1 ) + m * \text{sequence}(l-1,m).$$

---

$a_{2} = a_{1+1} \leq \max_{1 \leq i \leq 1}(a_{i}+1) $ which mean i can only be 1. Then $a_{2} \leq \max(2)$. and $a_{3}\leq \max(3)$.

Yes, $a_{2} \leq \max(2)=2$. However, $a_{3}\leq \max(a_1+1, a_2+1)$. If $a_2=1$, then $a_3\le \max(1+1, 1+1)=2$. While $a_3\le \max(3)=3$ is true, it might be relaxed too much.

---

Let us see how we are going to fill the two dimensional array sequence($m$,$l$).

For example, how to use the following relation? $$\text{sequence}(4,4) = \text{sequence}(3, 3 ) + 4 * \text{sequence}(3,4)\,.$$ We know sequence$(3,3) = 1$ since there is only one sequence of length 3 and maximum number 3, $[1,2,3]$ or sequence$(3,3) = 1 + 3 * 0 = 1$. There is no sequence of length of length 3 and maximum number 4, since the maximum number in any sequence of length 3 is at most 3. So $$\text{sequence}(4,4) = 1 + 4 * 0 = 1\,,$$ which corresponds to the unique sequence of length 4 and maximum number 4, $[1,2,3,4]$.

---

What is exactly $m$ in $\text{sequence}(l, m)$? Where should we place $a_4$ in the table of $l * m$?

It looks like you need to understand the recurrence relation.

$$ \text{sequence}(l,m) = \text{sequence}(l-1, m-1 ) + m * \text{sequence}(l-1,m),$$

where $\text{sequence}(l,m)$, $l\ge2$, $m\ge1$ is the number of sequences whose length is $l$ and whose maximum number is $m$. For example, a sequence $(a_1, a_2,a_3,a_4)$ is a sequence of length 4 and whose maximum number is $\max(a_1, a_2,a_3,a_4)$. If that maximum number is $k$, it contributes 1 to $\text{sequence}(4, k)$ if it satisfies the two conditions. For example, sequence $(1,2,3,2)$ contributes 1 to $\text{sequence}(4, 3)$ while sequence $(1,1,2,2)$ contributes 1 to $\text{sequence}(4, 2)$.

Let $a_1, a_2, \cdots, a_l$ be such a sequence. Let us consider its first $l-1$ items, $a_1, a_2,\cdots, a_{l-1}$.

• The maximum number of $a_1, a_2,\cdots, a_{l-1}$ is smaller than $m-1$. Then $$a_{l} = a_{(l-1)+1}\leq \max_{1\le i \le l-1} (a_{i}+1) = 1+\max_{1\le i \le l-1} a_{i}\lt m$$, which contradicts that fact that the maximum number of all of them is $m.

  So this situation cannot happen.

• The maximum number of $a_1, a_2,\cdots, a_{l-1}$ is $m-1$. Then $a_l$ must be $m$. Otherwise, the maximum number of the whole sequence will be $m-1$ instead of the required $m$.

  So for each sequence counted in $\text{sequence}(l-1, m-1 )$, we have a sequence that should be counted in $\text{sequence}(l, m)$. We have a summand $\text{sequence}(l-1, m-1)$

• The maximum number of $a_1, a_2,\cdots, a_{l-1}$ is $m$. Then $a_l$ can be anyone of $1, 2, \cdots, m$ $m$. So for each sequence counted in $\text{sequence}(l-1, m)$, we have $m$ sequences that should be counted in $\text{sequence}(l, m)$. That is, we have a summand $ m * \text{sequence}(l-1, m)$.

Combining all three cases above, we obtain that recurrence relation.