Number Of Ways To Traverse Graph

• Time : O(wh)
• Space : O(min(w, h))

using namespace std;

int numberOfWaysToTraverseGraph(int width, int height) {
	if(width > height) return numberOfWaysToTraverseGraph(height, width);
  vector<int> dp(width, 1);
	for(int i = 1; i < height; i++) {
		for(int j = 1; j < width; j++) {
			dp[j] += dp[j-1];
		}
	}
  return dp.back();
}

• Time : O(w + h)
• Space : O(1)

using namespace std;

int fact(int n) {
	if(n == 0) return 0;
	if(n == 1) return 1;
	return n * fact(n - 1);
}

int numberOfWaysToTraverseGraph(int width, int height) { // nCr concepts
	if(height == 1 or width == 1) return 1;
	int n = width - 1 + height - 1;
	int r = min(width - 1, height - 1);
  return (int)(fact(n) / (fact(r) * fact(n-r)));
}