We have $n$ objects. (They are similar, like $n$ nuts)
The objective is to arrange these objects in some columns beside each other such that the height of each column is more than the height of its previous column.
Using the Dynamic Programming approach, Provide an algorithm of $O(n^3)$ for finding the number of possible arrangements of these objects.
I was thinking of dividing the problem into some subproblems and storing the result of them in an array. But, i don't know how! So, i'm stuck... I'm not sure if i'm thinking the right way...
Any idea? Can u provide an algorithm?
This is not a solution, but a suggestion of one possible way to think about the problem in terms of triangular numbers.
The $m$-th triangular number is defined as
$$ T_m=1+2+3+\cdots+m=\frac{m(m+1)}{2}$$
A triangular number of objects has a canonical stacking $\mathcal{S}_m$ where each column contains exactly one more object than the column to its right.
Suppose $k$ is a positive integer and
$$ T_m<k<T_{m+1}$$
Then call the canonical stacking of $\mathcal{S}_k$ of $k$ the canonical stacking of $m$ with one of the $m-k$ excess objects placed on the leftmost column of $\mathcal{S}_m$, one on the next column to the right, etc until all $m-k$ excess objects are exhausted.
In this manner there is only one canonical stacking $\mathcal{S}_k$ for each positive integer $k$.
Now all other stackings satifying the condition may be viewed as a canonical stacking for some $k$ with one or more columns removed to produce a substacking $\mathcal{S}_k^\prime$ of $\mathcal{S}_k$.
So for each canonical stacking for $k$ objects, how many substackings are there and how many objects are in each substacking?
Note that for each $k$ one should not count substackings already considered for smaller values of $k$. One should only consider substackings which include the leftmost column of the stacking.
Offered solely as one possible way of thinking about the exercise.
Addendum: I just noticed (what should have been immediately obvious) that if $T_m<k<T_{m+1}$ then $\mathcal{S}_k$ is a substacking of $\mathcal{S}_{m+1}$ with a single column removed.
Update
There is a one-to-one correspondence between each positive binary integer and the possible stack arrangements.
The first stack pictured is a full stack which contains all $n$ columns. Included columns are associated with a $1$ bit and absent columns with a $0$ bit. Since the full $n-stack$ has all $n$ columns present it is represented by a binary string of $n$ $1$'s, so the full $n-stack$ is associated uniquely with the binary number $2^n-1$.
For further explanation the second diagram shows the sub-stack $\mathcal{S}_{45}$ of the $6-stack$.
The full $6$-stack is $\mathcal{S}_{63}$.
The smallest $m$-stack containing at least $n$ blocks is is $m=\left\lceil\dfrac{-1+\sqrt{8n}}{2}\right\rceil$ and the largest is $m=n$. For the $n$-stack, there is only one sub-stack containing exactly $n$ blocks, namely $\mathcal{S}_{2^{n-1}}$.
As for designing a counting algorithm of order $\mathcal{O}(n^3)$ using the Dynamic Programming approach, I have no idea. I learned to program in Fortran in 1962 and other than Fortran 95, bc and Javascript I have not used any of the more modern languages or techniques.
But I hope this method of associating each stack with a unique binary number can prove useful.