Número de formas de obtener una suma dada con n número de dados de m caras

Dados n dados, cada uno con m caras, numerados del 1 al m, encuentra el número de formas de obtener una suma dada X. X es la suma de los valores en cada cara cuando se lanzan todos los dados.
Ejemplos: 
 

Entrada: caras = 4 tiros = 2 suma =4 
Salida: 3 
formas de alcanzar una suma igual a 4 en 2 tiros puede ser {(1, 3), (2, 2), (3, 1) }
Entrada: caras = 6 lanzamientos = 3 suma = 12 
Salida: 25
 

Enfoque: 
Básicamente, se pide lograr la suma en n número de operaciones usando los valores en el rango [1…m]. 
Utilice la metodología top-down de programación dinámica para este problema. Los pasos son: 
 

• Casos básicos: 
  1. Si (sum == 0 y noofthrowsleft ==0) devuelve 1 . Significa que se 
     ha logrado la suma x.
  2. Si (suma < 0 y noofthrowsleft ==0) devuelve 0. Significa que la suma x no se 
     ha logrado en todos los lanzamientos.
• Si ya se logró la suma actual con el número actual de lanzamientos, devuélvala de la tabla en lugar de volver a calcularla.
• Luego recorreremos todos los valores de las caras desde i=[1..m] y nos moveremos recursivamente para lograr sum-i y también disminuiremos los noofthrowsleft en 1.
• Finalmente, almacenaremos los valores actuales en la array dp

A continuación se muestra la implementación del método anterior: 
 

// C++ function to calculate the number of
// ways to achieve sum x in n no of throws
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
int dp[55][55];
 
// Function to calculate recursively the
// number of ways to get sum in given
// throws and [1..m] values
int NoofWays(int face, int throws, int sum)
{
    // Base condition 1
    if (sum == 0 && throws == 0)
        return 1;
 
    // Base condition 2
    if (sum < 0 || throws == 0)
        return 0;
 
    // If value already calculated dont
    // move into re-computation
    if (dp[throws][sum] != -1)
        return dp[throws][sum];
 
    int ans = 0;
    for (int i = 1; i <= face; i++) {
 
        // Recursively moving for sum-i in
        // throws-1 no of throws left
        ans += NoofWays(face, throws - 1, sum - i);
    }
 
    // Inserting present values in dp
    return dp[throws][sum] = ans;
}
 
// Driver function
int main()
{
    int faces = 6, throws = 3, sum = 12;
 
    memset(dp, -1, sizeof dp);
 
    cout << NoofWays(faces, throws, sum) << endl;
 
    return 0;
}

// Java function to calculate the number of
// ways to achieve sum x in n no of throwsVal
class GFG
{
 
    static int mod = 1000000007;
    static int[][] dp = new int[55][55];
 
    // Function to calculate recursively the
    // number of ways to get sum in given
    // throwsVal and [1..m] values
    static int NoofWays(int face, int throwsVal, int sum)
    {
        // Base condition 1
        if (sum == 0 && throwsVal == 0)
        {
            return 1;
        }
 
        // Base condition 2
        if (sum < 0 || throwsVal == 0)
        {
            return 0;
        }
 
        // If value already calculated dont
        // move into re-computation
        if (dp[throwsVal][sum] != -1)
        {
            return dp[throwsVal][sum];
        }
 
        int ans = 0;
        for (int i = 1; i <= face; i++)
        {
 
            // Recursively moving for sum-i in
            // throwsVal-1 no of throwsVal left
            ans += NoofWays(face, throwsVal - 1, sum - i);
        }
 
        // Inserting present values in dp
        return dp[throwsVal][sum] = ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int faces = 6, throwsVal = 3, sum = 12;
        for (int i = 0; i < 55; i++)
        {
            for (int j = 0; j < 55; j++)
            {
                dp[i][j] = -1;
            }
        }
 
        System.out.println(NoofWays(faces, throwsVal, sum));
    }
}
 
// This code is contributed by 29AjayKumar

# Python3 function to calculate the number of
# ways to achieve sum x in n no of throws
import numpy as np
 
mod = 1000000007;
 
dp = np.zeros((55,55));
 
# Function to calculate recursively the
# number of ways to get sum in given
# throws and [1..m] values
def NoofWays(face, throws, sum) :
 
    # Base condition 1
    if (sum == 0 and throws == 0) :
        return 1;
 
    # Base condition 2
    if (sum < 0 or throws == 0) :
        return 0;
 
    # If value already calculated dont
    # move into re-computation
    if (dp[throws][sum] != -1) :
        return dp[throws][sum];
 
    ans = 0;
    for i in range(1, face + 1) :
 
        # Recursively moving for sum-i in
        # throws-1 no of throws left
        ans += NoofWays(face, throws - 1, sum - i);
 
    # Inserting present values in dp
    dp[throws][sum] = ans;
     
    return ans;
 
 
# Driver function
if __name__ == "__main__" :
 
    faces = 6; throws = 3; sum = 12;
 
    for i in range(55) :
        for j in range(55) :
            dp[i][j] = -1
 
    print(NoofWays(faces, throws, sum)) ;
     
# This code is contributed by AnkitRai01

// C# function to calculate the number of
// ways to achieve sum x in n no of throwsVal
using System;
 
class GFG
{
     
    static int[,]dp = new int[55,55];
 
    // Function to calculate recursively the
    // number of ways to get sum in given
    // throwsVal and [1..m] values
    static int NoofWays(int face, int throwsVal, int sum)
    {
        // Base condition 1
        if (sum == 0 && throwsVal == 0)
        {
            return 1;
        }
 
        // Base condition 2
        if (sum < 0 || throwsVal == 0)
        {
            return 0;
        }
 
        // If value already calculated dont
        // move into re-computation
        if (dp[throwsVal,sum] != -1)
        {
            return dp[throwsVal,sum];
        }
 
        int ans = 0;
        for (int i = 1; i <= face; i++)
        {
 
            // Recursively moving for sum-i in
            // throwsVal-1 no of throwsVal left
            ans += NoofWays(face, throwsVal - 1, sum - i);
        }
 
        // Inserting present values in dp
        return dp[throwsVal,sum] = ans;
    }
 
    // Driver code
    static public void Main ()
    {
        int faces = 6, throwsVal = 3, sum = 12;
        for (int i = 0; i < 55; i++)
        {
            for (int j = 0; j < 55; j++)
            {
                dp[i,j] = -1;
            }
        }
 
    Console.WriteLine(NoofWays(faces, throwsVal, sum));
    }
}
 
// This code is contributed by ajit.

<script>
 
// Javascript function to calculate the number of
// ways to achieve sum x in n no of throws
 
const mod = 1000000007;
let dp = new Array(55);
for (let i = 0; i < 55; i++)
    dp[i] = new Array(55).fill(-1);
 
// Function to calculate recursively the
// number of ways to get sum in given
// throws and [1..m] values
function NoofWays(face, throws, sum)
{
    // Base condition 1
    if (sum == 0 && throws == 0)
        return 1;
 
    // Base condition 2
    if (sum < 0 || throws == 0)
        return 0;
 
    // If value already calculated dont
    // move into re-computation
    if (dp[throws][sum] != -1)
        return dp[throws][sum];
 
    let ans = 0;
    for (let i = 1; i <= face; i++) {
 
        // Recursively moving for sum-i in
        // throws-1 no of throws left
        ans += NoofWays(face, throws - 1, sum - i);
    }
 
    // Inserting present values in dp
    return dp[throws][sum] = ans;
}
 
// Driver function
    let faces = 6, throws = 3, sum = 12;
    document.write(NoofWays(faces, throws, sum));
 
</script>

25

Complejidad temporal : O(lanzamientos*caras*suma) 
Complejidad espacial : O(caras*suma)