CareerCup

Naive recursion will be O(2^(max(N, M)). With dynamic programming you can make it O(N*M) which is a *HUGE* improvement.

Going from recursive approach to DP is not very hard if you think about the recursion tree.

C++ implementation with naive recursion and DP approach:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

unsigned scheduler_possibilities(unsigned m, unsigned n) {
	if (m == 0 || n == 0) {
		return 1;
	}
	return scheduler_possibilities(m-1, n)+scheduler_possibilities(m, n-1);
}

unsigned scheduler_possibilities_dp(unsigned m, unsigned n) {
	unsigned dim = max(m+1, n+1);
	vector<vector<unsigned> > dp(dim, vector<unsigned>(dim));

	for (size_t i = 0; i < dim; i++) {
		dp[i][0] = 1;
		dp[0][i] = 1;
	}

	for (size_t i = 1; i < dim; i++) {
		for (size_t j = 1; j < dim; j++) {
			dp[i][j] = dp[i-1][j]+dp[i][j-1];
		}
	}

	return dp[m][n];
}

int main(void) {
	cout << "Enter M and N" << endl;
	cout << "> ";

	unsigned m, n;
	while (cin >> m >> n) {
		//cout << scheduler_possibilities(m, n) << endl;
		cout << scheduler_possibilities_dp(m, n) << endl << "> ";
	}

	return 0;
}

This can be written in a recursive fashion as such:

F(M, N) = F(M- 1, N) + F(M, N- 1)

Because we have to maintain the order of processes. If we started with Ma, next could either be Mb or Na (which is represented by F(M- 1, N)). Likewise, if we start with Na, next could either be Nb or Ma (which is represented by F(M, N - 1)).


In code, something like this could work:

public int num(int m, int n) {
	
	if (m <  0 || n < 0) {

		return 0;
	}

	if (m == 0) {

		return 1;
	}

	if (n == 0) {

		return 1;
	}

	return num(m , n-1) + num (m - 1, n);

}

We can then memoize to make it more efficient.

@SK, these are combinations, i.e., C(M + N, N) or C(M + N, M)

indeed, since the order of instructions of one program is fixed, we denote
by 0's the instructions of the 1st program and by 1's - the instructions of the 2nd
Hence the problem reduces to computing the # of ways how to set M ones having M+N places which is combinations.

Example: M = 3, N = 2.
11100 -> Ma Mb Mc Na Nb
01101 -> Na Ma Mb Nb Mc
... etc