!! how is this related to the CSY staircase problem?
Q: given K dollars and N distinct mutual funds (including a cash fund), how many unique allocation strategies are there? It’s permissible to allocate $0 to any fund, but total amount in a strategy must add up to exactly K dollars
Note K can be higher or lower than N, both positive integers. Allocation amount must be whole dollars.
Without loss of generality, let’s say K is $5 and N is 3.
I think this is more a mathematical than an algorithm question. Each strategy can be represented by an N-element array. [0,5,0] is one strategy, allocation $5 to 2nd fund and $0 to the other funds. If we are required to enumerate all the strategies, we can print out the arrays.
My solution starts by defining a mathematical function f(k, n) := count of allocation strategies given k dollars and n funds. Based on such a definition, we can see
- f(any_integer, 1) == 1 because there’s only one fund to receive the full amount. One strategy only.
- f(0, any_integer) == 1 because all funds must receive $0 each. No other strategy.
Without loss of generality, let’s say K is 33 and N is 21. Using bottom-up DP, I assert that when we get a “new” fund, the 22nd fund, we can use the earlier answers to find f(33,22):
f($33,22) = f($33,21)f($0,1) + f($32,21)f($1,1) + f($31,21)f($2,1) +… +f($1,21)f($32,1)+f($0,21)f($33,1)
Let me explain the 3rd term on the right-hand-side. This term means the count for “$31 into the 21 existing funds” multiplied by the count for “$2 into the new fund”. This describes the scenario of first allocating $2 to the new fund, and then allocating the remaining $31 to the existing funds. The above formula simplifies to
f($33,22) = f($33,21) + f($32,21) + f($31,21) +… + f($1,21) +1
This formula for f(33,22) uses earlier results for f(smaller or equal amounts, one fund fewer). A bottom-up DP algorithm is straightforward. Generalization of this example gives
f(K,n+1) = f(K,n) + f(K-1,n) + f(K-2,n) + f(K-3,n)+..+ f(2,n) + f(1,n) + f(0,n)