Binomial Coefficients using Dynamic Programming
The intuition behind it.
A Binomial equation like (x+y)²(Or equations of similar forms) are solvable quite easily as there are simplified formulas to solve them. But what if we are given a formula like (3a+2b)⁶ ? It becomes quite a hassle, if not downright monotonous to expand and simplify it. Not only does it consume a lot of time, but also prone to lot of errors. To solve similar(and worse) equations, we summon the binomial theorem of Discrete Math.
Let us explore how this theorem of binomial coefficients can help us solve bigger binomial equations. The binomial theorem states the principle for expanding the algebraic expression (x + y)^n and expresses it as a sum of the terms involving individual exponents of variables x and y. Each term in a binomial expansion is associated with a numeric value which is called coefficient[¹]. According to the Binomial Theorem, a binomial equation of the form (x+y) to the power of n can be written as:
where n is a positive integer.
Consider the example (3a+2b)⁶.
if 3a is considered as x and 2b is considered as y, this can be solved using binomial theorem by doing the following.
using the formula of combinatorics, we can solve the combinations.
Notice however that the coefficients are forming a pattern here. (1,6,15,20,15,6,1). This is because of the property of symmetry in combinations. nCr = nCn-r.
Moreover, this pattern can be derived from the Pascal’s triangle.
The rows of a pascal’s triangle are numbered from 0 to n. Therefore a binomial equation to the power n, will get its coefficients from the (n+1)th row.
As evident from the above image, each coefficient is dependent on the upper two elements. This gives us a recurrence relation of[²],
C[i][j] = C[i-1][j-1] + C[i-1][j]
C[0][0] = 1
int binomialCoeff(int i, int j){
if(j == 0 || j == i) return 1;
return binomialCoeff(i-1, j-1) + binomialCoeff(i-1,j);
}Recursion tree for the above relation would look something like,
It is evident that there is some re-computation going on, which will increase exponentially as we input greater values. Therefore, we memoize the results of overlapping subproblems in-order to avoid the re-computation. A simple bottom-up DP approach is shown below:
state: dp[i][j] => number of ways to chose j elements from i places.
transition: dp[i][j] = dp[i-1][j-1] + dp[i-1][j]int binomialCoeff(int n, int k){
vector<vector<int>> dp2(1000, vector<int>(1000, 0));
dp2[0][0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++){
dp2[i][j] = dp[i-1][j-1] + dp[i-1][j];
}
}
return dp[n][k];
}
This C[i][j] gives us the number of ways to select j numbers from a set of i positions. Let’s visualize the dp table for the above computation.
Notice that, the bottom-up approach pushes the values gradually towards the cell which we are looking for. Although DP is intuitive to think about in terms of a recursive algorithm, the iterative approach is used more by most programmers due to its simplicity.
Intuition Behind it:
In order to understand the intuition behind the above recurrence relation, let us summon a problem to solve.
Consider a string of bits(‘0’ and ‘1’). We are asked to find the number of ways to create the string of length n, with exactly k ‘1’ bits. Obviously this is a combination problem as all we care about is, selecting k bits from a set of n bits. (n choose k)
Building a Solution: Think of it this way. At any index ‘i’ in the string, we have two choices to make. Either make this bit ‘1’ or make it ‘0’. If we have used all the ones in the value ‘k’, we would know that we have formed one of the required strings. This is a brute force or backtracking or DFS or complete search algorithm which generates all possibilities O(2^n). We can do better than this.
Notice that we do not care about the actual strings. What we do care about, is the count of them. Let’s introduce something here. Selecting every position as 1 or 0, means counting all the substrings starting from 0 and 1. Therefore, at every position, there will two sets — numbers that start with 0 and numbers that start with 1. This indeed will be the state of our DP.
Let us think about some smallest possible subproblems.
- Let’s say our string length is 0. Then no matter how big the value of k is, the total number of ways to create the string is always 1.
- The value k is 0 or it equals the value of n. Again in this case, the answer is just 1.
The above can be taken as our base cases. Now that we have our base cases defined, we can consider the bigger subproblems and define how they can be related to the smaller subproblems.
Recollecting the previous explanation, at every iteration, we count the substrings that start with 0 and the ones that start with 1. There are Nways(n-1, k) strings that start with 0 and Nways(n-1, k-1) strings that start with a 1.
Nways(n, k) = Nways(n-1, k) + Nways(n-1, k-1)
Now that we have our DP state, base cases and our transition defined, we can come up with an algorithm.
int Nways(int n, int k){
if(n == 0 || k == 0) return 1;
if(k == n) return 1;
return Nways(n-1, k) + Nways(n-1, k-1);
}
// apply memoization yourself :)Notice that, it is same code as above for finding binomial coefficients. Often time, the coding part is easy. It is the thinking and the intuition behind a solution which takes time to build.
Now let us solve a different version of the same problem. Instead of finding all the strings with exactly k bits set, we try to find all the strings with at most k bits set.
The only difference in this problem is, we care about all the possibilities until our k becomes 0. Therefore, the only difference here is we do not stop our search when the value k equals the length of our string(as our previous problem).
Let’s build upon our previous state.
state: Nways(n, k) = Number of ways to construct a string of bits with at most k bits set.
transition: Nways(n,k) = Nways(n-1, k) + Nways(n-1, k-1)Base Cases:
- When the length of the string is 0, we only have 1 ways to create a string regardless of the number k.
- When the value k becomes 0, there is no other possibility. Hence we return 1.
Look carefully at both the base cases. There is a subtle difference.
int Nways(int n, int k){
if(n == 0 || k == 0) return 1;
return Nways(n-1, k) + Nways(n-1, k-1);
}
// we removed one of the base cases.Here, 4C3 = 3C0 + 3C1 + 3C2 + 3C3. As the number of set bits asked is at most k.
Another interesting problem using the same intuition:
Given the length of a string of bits and k maximum number of 1 bits, we need to find the I’th binary number (string) from it. You can find this problem here.
In this problem, we have to print the exact string instead of just counting them.
A simple brute force algorithm would be to generate all possible strings from decimal 0 to 2^n, removing all the strings with number of 1s greater than k.
Using the Nways function we build just above, we can find the number of strings which have at most k bits set. According to the previous explanation, we have two parts — numbers starting with 0 and the numbers starting with 1.
So if at any index i, if the value I is greater that the total numbers of strings for the rest of the string, it must be obvious that our string starts with 1 at index i. (As, for a string of length 5, 10000 is bigger than the greatest possible string of length 4 i.e 1111).
Otherwise, if the value I is less than Nways(n-1, k), the string starts with a 0. Refer below image.
By following the above steps for the rest of the indices, we generate the I’th string in the set. You can find the source code here on my github.
I hope these problems gave some idea about the concept and helped in getting the intuition behind it (It surely did for me). Share it if you found it helpful.🙂
References:
