Programación dinámica (DP): ¿Cuál es el número total de formas en que N dados pueden sumar S?

Answer 1

Hay dos posibles respuestas a esto, dependiendo de si los dados son distinguibles. Por ejemplo, si tienes dos dados, ¿cuál es la cantidad de formas de lanzar un 11? Si son distinguibles, la respuesta es 2. Puedes tirar 5, 6 o puedes tirar 6, 5. Si no son distinguibles, entonces la única forma de lanzar un 11 es tirar un 5 y un 6, entonces La respuesta es una. Necesitaremos programas dinámicos bastante diferentes para resolver cada uno.

Para dados distinguibles, escribiremos un programa dinámico similar al mencionado en los detalles de la pregunta. Sea [math] N [d, s] [/ math] el número de formas de tirar dados [math] d [/ math] y obtener una suma de [math] s [/ math]. Entonces podemos hacer una suma basada en el resultado del primer dado, [matemáticas] N [d, s] = \ sum \ limits_ {i = 1} ^ {6} N [d-1, si] [/ matemáticas] . Esto proporciona la cantidad de formas de obtener el resto de la suma dado el resultado del primer dado. Solo necesitamos dos casos base, [matemática] N [0, 0] = 1 [/ matemática] y [matemática] N [0, s] = 0 [/ matemática] para [matemática] s \ ne 1 [/ matemática] porque 0 dados no pueden dar una suma distinta de cero. Para acelerar las cosas y evitar exceder los límites de su tabla DP, también puede usar [math] N [d, s] = 0 [/ math] para [math] s 6d [/ matemáticas]. Este DP toma [math] O (d \ cdot s) [/ math] tiempo y [math] O (s) [/ math] espacio si no mantiene los datos para un número de dados menor que [math] d- 1 [/ math] mientras calcula la respuesta para [math] d [/ math].

Para los dados indistinguibles, en su lugar, necesitamos contar cuántos dados pueden tener cada valor. Definiremos [matemática] I [d, v, s] [/ matemática] como el número de formas en que [matemática] d [/ matemática] los dados indistinguibles pueden sumar a [matemática] s [/ matemática] sin ninguna de las ellos muestran un valor mayor que [math] v [/ math]. Ahora haremos una suma basada en cuántos dados muestran [math] v [/ math]. Tenemos [matemática] I [d, v, s] = \ sum \ limits_ {i = 0} ^ {d} I [di, v-1, s-vi] [/ math]. Los casos base son [matemática] I [0, v, 0] = 1 [/ matemática] y [matemática] I [0, v, s] = 0 [/ matemática] para [matemática] s \ ne 1 [/ matemática ] También puede cortar los cálculos cuando [math] s dv [/ math]. Este DP toma [math] O (d ^ 2 \ cdot s) [/ math] tiempo y [math] O (d \ cdot s) [/ math] espacio.