Time complexity of number of solutions to equation of varying size, with varying upper-bound range restrictions I solved this problem: Number of solutions to equation of varying size, with varying upper-bound range restrictions in Python by using generating functions. The solution is described in more detail in the comment section of David's answer here: https://stackoverflow.com/questions/69468913/given-n-balls-and-m-bins-each-bin-with-a-certain-capacity-how-many-combination/69470209?noredirect=1#comment122792101_69470209
I am wondering however, how does one calculate the time complexity of such a solution? Please explain it to me like you would to a child, if possible.
Is there any way to improve the time complexity? If so, how? I'm trying to think of a solution that includes memorization but cannot quite think of one. Any ideas?
 A: Here is an $O(mn)$ algorithm. It appears different from the generating function approach, but it is "morally the same," while being easier to implement and describe the runtime of.
Note that the inclusion-exclusion approach described here takes something like $O(m2^m)$ time, so you should prefer to use that algorithm if $n$ is much larger than $2^m$.

You are given a list $L=[C_1,C_2,\dots,C_m]$ of the bin capacities, and want to count the number of solutions to
$$
\begin{cases}
x_1+x_2+\dots+x_m=n \\
x_k\in \{0,1,\dots,C_k\}\text{ for each }k\in \{1,\dots,m\}
\end{cases}
$$
For each $i\in \{1,\dots,m\}$, and each $j\in \{0,\dots,n\}$, let
$$
F(i,j)=\text{ # of solutions to }
\begin{cases}
x_1+x_2+\dots+x_{\color{red}i}=\color{blue}j \\
x_k\in \{0,1,\dots,C_k\}\text{ for each }k\in \{1,\dots,m\}
\end{cases}
$$
That is, $F(i,j)$ is the number of solutions to the smaller problem where you only deal with the first $i$ variables, and the target sum is a possibly smaller number $j$. The overall goal is to compute $F(m,n)$.
The reason for considering $F(i,j)$ is the following: we have that
$$
F(i,j)=F(i-1,j)+F(i-1,j-1)+F(i-1,j-2)+\dots+F(i-1,j-C_i)\tag1
$$
This follows by considering all possibilities for the variable $x_i$. If $x_i=a$, then the first $i-1$ variables have to add up to $j-a$, which can be done in $F(i-1,j-a)$ ways. The equation $(1)$ actually implies a simpler equation, which is better for computational purposes:
$$
F(i,j)=F(i,j-1)+F(i-1,j)-F(i-1,j-C_i-1)\tag2
$$
As with any recursive equation, you need base cases:
$$
F(1,j)=\begin{cases}1 & 0\le j \le C_1 \\ 0 & \text{otherwise}\end{cases}\qquad\;\;\;\;
\\
F(i,j)=0 \qquad \text{when $j$ is negative}\tag3
$$
Anyways, using equation $(2)$, and the base cases in $(3)$, you can compute $F(m,n)$ by filling out the $m\times (n+1)$ DP table whose entry in the $i^{th}$ row and $j^{th}$ column is $F(i,j)$.
