[toph.co] Counting Murgis

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Counting Murgis
Source            : toph.co
Category          : Dynamic Programing
Algorithm         : 
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
using ll = long long;
 
ll dp[22][22]; // dp[ taken ][ last ]
bool memoize[22][22];
 
int n, k;
 
inline ll solve(int taken = 0, int last = 0)
{
	if (taken >= k) return 1;
	ll &ret = dp[taken][last];
	bool &mem = memoize[taken][last];
	if (mem) return ret;
	mem = 1;
	ll sum = 0;
	for (int i = 0; i < n; i++)
	{
		if (i > last) sum += solve(taken+1, i);
	}
	return ret = sum;
}
 
int main()
{
	int tc;
	cin >> tc;
	for (int tcase = 1; tcase <= tc; tcase++)
	{
		cin >> n >> k;
		memset(memoize, 0, sizeof memoize);
		cout << solve() << "\n";
	}
}