# count allocation strategies of \$K into N funds #70%

!! 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.

====Analysis

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)