Given N dice each with M faces, numbered from 1 to M, find the number of ways to get sum X. X is the summation of values on each face when all the dice are thrown.
 
Example 1:
Input:
M = 6, N = 3, X = 12
Output:
25
Explanation:
There are 25 total ways to get
the Sum 12 using 3 dices with
faces from 1 to 6.
Example 2:
Input:
M = 2, N = 3, X = 6
Output:
1
Explanation:
There is only 1 way to get
the Sum 6 using 3 dices with
faces from 1 to 2. All the
dices will have to land on 2.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function noOfWays() which takes 3 Integers M,N and X as input and returns the answer.
 
Expected Time Complexity: O(M*N*X)
Expected Auxiliary Space: O(N*X)
 
Constraints:
1 <= M,N,X <= 50

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def noOfWays(self, M, N, X):

        # code here

Solutions:
class Solution:

	def noOfWays(self, M, N, X):
		curr = [0 for i in range(X + 1)]
		prev = [0 for j in range(X + 1)]
		prev[0] = 1
		for dice in range(1, N + 1):
			for target in range(1, X + 1):
				ans = 0
				for i in range(1, M + 1):
					if target - i >= 0:
						ans = ans + prev[target - i]
				curr[target] = ans
			prev = curr
			curr = [0 for i in range(X + 1)]
		return prev[X]


class Solution:

	def noOfWays(self, M, N, X):
		dp = [[-1 for i in range(X + 1)] for j in range(N + 1)]
		return self.solve(N, M, X, dp)

	def solve(self, dice, face, target, dp):
		if target < 0:
			return 0
		if dice == 0 and target != 0:
			return 0
		if target == 0 and dice != 0:
			return 0
		if dice == 0 and target == 0:
			return 1
		if dp[dice][target] != -1:
			return dp[dice][target]
		ans = 0
		for i in range(1, face + 1):
			ans = ans + self.solve(dice - 1, face, target - i, dp)
		dp[dice][target] = ans
		return dp[dice][target]


class Solution:

	def solve(self, dices, faces, target, dp):
		if target < 0:
			return 0
		if dices == 0 and target != 0:
			return 0
		if target == 0 and dices != 0:
			return 0
		if target == 0 and dices == 0:
			return 1
		if dp[dices][target] != -1:
			return dp[dices][target]
		count = 0
		for i in range(1, faces + 1):
			ans = self.solve(dices - 1, faces, target - i, dp)
			count = count + ans
		dp[dices][target] = count
		return dp[dices][target]

	def noOfWays(self, M, N, X):
		dp = [[-1] * (X + 1) for _ in range(N + 1)]
		ans = self.solve(N, M, X, dp)
		return ans


class Solution:

	def noOfWays(self, M, N, X):

		def solveTab(N, M, X):
			cur = [0 for i in range(X + 1)]
			pre = [0 for i in range(X + 1)]
			pre[0] = 1
			for index in range(1, N + 1):
				for target in range(1, X + 1):
					ans = 0
					for i in range(1, M + 1):
						if target - i >= 0:
							ans = ans + pre[target - i]
						cur[target] = ans
				pre = cur
				cur = [0 for i in range(X + 1)]
			return pre[X]

		def solve(index, faces, target, dp):
			if target < 0:
				return 0
			if target == 0 and index != 0:
				return 0
			if target != 0 and index == 0:
				return 0
			if target == 0 and index == 0:
				return 1
			if dp[index][target] != -1:
				return dp[index][target]
			ans = 0
			for i in range(1, faces + 1):
				ans = ans + solve(index - 1, faces, target - i, dp)
			dp[index][target] = ans
			return ans
		dp = [[-1 for i in range(X + 1)] for j in range(N + 1)]
		return solveTab(N, M, X)


class Solution:

	def noOfWays(self, M, N, X):
		num_ways = 0
		if X < N:
			return 0
		dp_table = [[0 for j in range(X + 1)] for i in range(N + 1)]
		for i in range(1, M + 1):
			if i <= X:
				dp_table[1][i] = 1
		for dice_idx in range(2, N + 1):
			for val in range(1, X + 1):
				for face_val in range(1, M + 1):
					if face_val <= val:
						if dp_table[dice_idx - 1][val - face_val]:
							dp_table[dice_idx][val] += dp_table[dice_idx - 1][val - face_val]
		return dp_table[-1][X]


class Solution:

	def noOfWays(self, M, N, X):
		d = [[0 for i in range(X)] for j in range(N)]
		for i in range(N):
			for j in range(X):
				if i == 0:
					if j < M:
						d[i][j] = 1
					else:
						d[i][j] = 0
				elif i > j:
					d[i][j] = 0
				elif j > M:
					d[i][j] = d[i][j - 1] + d[i - 1][j - 1] - d[i - 1][j - 1 - M]
				else:
					d[i][j] = d[i][j - 1] + d[i - 1][j - 1]
		return d[N - 1][X - 1]


class Solution:

	def solve(self, M, dice, target):
		if dice == 0 and target == 0:
			return 1
		if dice != 0 and target == 0 or (dice == 0 and target != 0):
			return 0
		ans = 0
		for i in range(1, M + 1):
			ans += self.solve(M, dice - 1, target - i)
		return ans

	def solve_memo(self, M, dice, target, F):
		if dice == 0 and target == 0:
			F[dice][target] = 1
			return F[dice][target]
		if dice != 0 and target == 0 or (dice == 0 and target != 0) or target < 0:
			return 0
		if F[dice][target] != -1:
			return F[dice][target]
		ans = 0
		for i in range(1, M + 1):
			ans += self.solve_memo(M, dice - 1, target - i, F)
		F[dice][target] = ans
		return F[dice][target]

	def solve_tab(self, M, N, X):
		F = [[0 for _ in range(X + 1)] for _ in range(N + 1)]
		F[0][0] = 1
		for dice in range(1, N + 1):
			for target in range(1, X + 1):
				ans = 0
				for i in range(1, M + 1):
					if target - i >= 0:
						ans += F[dice - 1][target - i]
				F[dice][target] = ans
		return F[N][X]

	def solve_tab2(self, M, N, X):
		curr = [0 for _ in range(X + 1)]
		prev = [0 for _ in range(X + 1)]
		prev[0] = 1
		for dice in range(1, N + 1):
			for target in range(1, X + 1):
				ans = 0
				for i in range(1, M + 1):
					if target - i >= 0:
						ans += prev[target - i]
				curr[target] = ans
			prev = curr[:]
		return prev[X]

	def noOfWays(self, M, N, X):
		return self.solve_tab2(M, N, X)


class Solution:

	def solve(self, M, dice, target):
		if dice == 0 and target == 0:
			return 1
		if dice != 0 and target == 0 or (dice == 0 and target != 0):
			return 0
		ans = 0
		for i in range(1, M + 1):
			ans += self.solve(M, dice - 1, target - i)
		return ans

	def solve_memo(self, M, dice, target, F):
		try:
			if dice == 0 and target == 0:
				F[dice][target] = 1
				return F[dice][target]
			if dice != 0 and target == 0 or (dice == 0 and target != 0) or target < 0:
				return 0
			if F[dice][target] != -1:
				return F[dice][target]
			ans = 0
			for i in range(1, M + 1):
				ans += self.solve_memo(M, dice - 1, target - i, F)
			F[dice][target] = ans
			return F[dice][target]
		except Exception as e:
			print('Error: ', dice, target)

	def noOfWays(self, M, N, X):
		F = [[-1 for _ in range(X + 1)] for _ in range(N + 1)]
		return self.solve_memo(M, N, X, F)


class Solution:

	def noOfWays(self, M, N, X):
		dp = [[0 for i in range(X + 1)] for i in range(N + 1)]
		dp[0][0] = 1
		for n in range(1, N + 1):
			for x in range(1, X + 1):
				ans = 0
				for i in range(1, M + 1):
					if x - i >= 0:
						ans = ans + dp[n - 1][x - i]
				dp[n][x] = ans
		return dp[N][X]


class Solution:
	dp = [[None for i in range(0, 51)] for j in range(0, 51)]

	def find(self, arr, n, count, sum_):
		if count == 0 and sum_ == 0:
			return 1
		elif count <= 0:
			return 0
		elif sum_ <= 0:
			return 0
		if self.dp[count][sum_] != None:
			return self.dp[count][sum_]
		x = 0
		for i in range(0, n):
			x = x + self.find(arr, n, count - 1, sum_ - arr[i])
		self.dp[count][sum_] = x
		return x

	def noOfWays(self, M, N, X):
		self.dp = [[None for i in range(0, 51)] for j in range(0, 51)]
		list_ = list(range(1, M + 1))
		return self.find(list_, len(list_), N, X)


class Solution:

	def noOfWays(self, M, N, X):
		if M * N < X:
			return 0
		dp = [[0 for inner in range(X + 1)] for outer in range(N + 1)]
		for i in range(1, X + 1):
			if i > M:
				break
			dp[1][i] = 1
		for n in range(2, N + 1):
			for x in range(n, X + 1):
				for m in range(1, M + 1):
					if m >= x:
						break
					dp[n][x] += dp[n - 1][x - m]
		return dp[N][X]


class Solution:

	def dice(self, M, N, X, dp):
		if N == 0 and X == 0:
			return 1
		if X <= 0:
			return 0
		if dp[N][X] != -1:
			return dp[N][X]
		ans = 0
		for i in range(1, M + 1):
			ans += self.dice(M, N - 1, X - i, dp)
		dp[N][X] = ans
		return ans

	def noOfWays(self, M, N, X):
		prev_dp = [0] * (X + 1)
		prev_dp[0] = 1
		for i in range(1, N + 1):
			dp = [0] * (X + 1)
			for j in range(1, X + 1):
				ans = 0
				for k in range(1, M + 1):
					if j - k >= 0:
						ans += prev_dp[j - k]
				dp[j] = ans
			prev_dp = dp
		return dp[-1]


class Solution:

	def solve(self, m, n, x, dp):
		if x == 0 and n == 0:
			return 1
		if n != 0 and x == 0:
			return 0
		if n == 0 and x != 0:
			return 0
		if x < 0:
			return 0
		if dp[n][x] != -1:
			return dp[n][x]
		ans = 0
		for i in range(1, m + 1):
			ans += self.solve(m, n - 1, x - i, dp)
		dp[n][x] = ans
		return dp[n][x]

	def noOfWays(self, M, N, X):
		dp = [[-1] * (X + 1) for _ in range(N + 1)]
		return self.solve(M, N, X, dp)


def solve(dice, faces, target, dp):
	if dice <= 0:
		if target == 0:
			return 1
		else:
			return 0
	if target <= 0:
		return 0
	if dp[dice][target] != -1:
		return dp[dice][target]
	ans = 0
	for i in range(1, faces + 1):
		ans = ans + solve(dice - 1, faces, target - i, dp)
	dp[dice][target] = ans
	return dp[dice][target]

class Solution:

	def noOfWays(self, M, N, X):
		dp = [[-1 for j in range(X + 2)] for i in range(N + 1)]
		return solve(N, M, X, dp)


class Solution:

	def noOfWays(self, M, N, X):

		def solve(remdices, remtarget):
			if remtarget < 0 or (remdices == 0 and remtarget != 0) or remdices < 0:
				return 0
			if remtarget == 0 and remdices == 0:
				return 1
			if dp[remdices][remtarget] != -1:
				return dp[remdices][remtarget]
			ways = 0
			for fvalue in range(1, M + 1):
				ways += solve(remdices - 1, remtarget - fvalue)
			dp[remdices][remtarget] = ways
			return dp[remdices][remtarget]
		dp = [[-1] * (X + 1) for i in range(N + 1)]
		return solve(N, X)


class Solution:

	def noOfWays(self, M, N, X):
		if X < N or X > M * N:
			return 0
		dp = dict()

		def rec(dice, x, M):
			if dice == 0:
				if x == 0:
					return 1
				return 0
			if (dice, x) in dp:
				return dp[dice, x]
			ans = 0
			for i in range(1, M + 1):
				if x >= i:
					ans += rec(dice - 1, x - i, M)
				else:
					break
			dp[dice, x] = ans
			return dp[dice, x]
		return rec(N, X, M)


class Solution:

	def noOfWays(self, M, N, X):
		store = {}

		def find(M, N, X):
			if X < N or X > N * M:
				return 0
			if N == 1:
				return 1
			if (N, X) in store:
				return store[N, X]
			s = 0
			for i in range(1, M + 1):
				s += find(M, N - 1, X - i)
			store[N, X] = s
			return s
		return find(M, N, X)


class Solution:

	def SolveMemoization(self, dice, face, target, memory):
		if target < 0:
			return 0
		if dice == 0 and target != 0:
			return 0
		if dice == 0 and target == 0:
			return 1
		if target == 0 and dice != 0:
			return 0
		if memory[dice][target] == -1:
			ans = 0
			for fce in range(1, face + 1):
				ans += self.SolveMemoization(dice - 1, face, target - fce, memory)
			memory[dice][target] = ans
		return memory[dice][target]

	def TopDp(self, n, m, x):
		memory = [[-1 for _ in range(x + 1)] for j in range(n + 1)]
		return self.SolveMemoization(n, m, x, memory)

	def BottomUp(self, n, m, x):
		memory = [[0 for _ in range(x + 1)] for j in range(n + 1)]
		memory[0][0] = 1
		for dice in range(1, n + 1):
			for target in range(1, x + 1):
				ans = 0
				for face in range(1, m + 1):
					ans += memory[dice - 1][target - face] if target >= face else 0
				memory[dice][target] = ans
		return memory[n][x]

	def BottomUpOptimized(self, n, m, x):
		current = [0 for _ in range(x + 1)]
		prev = [0 for _ in range(x + 1)]
		prev[0] = 1
		for dice in range(1, n + 1):
			for target in range(x, 0, -1):
				ans = 0
				for face in range(1, m + 1):
					ans += prev[target - face] if target >= face else 0
				current[target] = ans
			prev = current
		return current[x]

	def noOfWays(self, M, N, X):
		return self.BottomUpOptimized(N, M, X)