Cómo usar la programación dinámica para contar las formas en que podemos escribir un entero dado como una suma ordenada de enteros pequeños

Answer 1

Sea C [math] (n, m) [/ math] el número de formas de escribir [math] n [/ math] como una suma ordenada de enteros positivos que no exceden [math] m [/ math].

La forma básica de encontrar una recurrencia / resolver un problema de conteo usando programación dinámica es la siguiente:

Primero, imagina construir la solución de forma incremental, como una secuencia de pasos. Aquí, esto es natural, podemos elegir un elemento de la suma a la vez, de izquierda a derecha.

Luego, considera todas las posibilidades de lo que sucede en el primer paso. El primer número [matemático] i [/ matemático] que elijamos estará entre 1 y [matemático] \ min (n, m) [/ matemático], inclusive. (Por lo general, será entre 1 y [matemáticas] m [/ matemáticas], inclusive, pero para las pequeñas [matemáticas] n [/ matemáticas] también debemos asegurarnos de no exceder eso).

Cada elección de [math] i [/ math] nos da un conjunto diferente de soluciones. Más precisamente, esos conjuntos de soluciones son mutuamente disjuntos. Por lo tanto, podemos contar el número de soluciones en cada caso por separado, y luego simplemente las sumamos.

Entonces, veamos un caso particular. El primer elemento de la suma es [math] i [/ math]. Para finalizar la suma, tenemos que escribir [math] ni [/ math] como una suma de elementos que no exceda [math] m [/ math]. ¿Luce familiar? Debería, porque es el mismo problema que antes. Usando nuestra notación, hay formas [math] C (ni, m) [/ math] de hacerlo.

Esto nos lleva a la siguiente recurrencia:

• caso base: [matemática] C (0, m) = 1 [/ matemática], la única forma es la suma vacía
• caso recursivo: [matemática] \ forall n> 0: C (n, m) = \ sum_ {i = 1} ^ {\ min (n, m)} C (ni, m) [/ math]

La evaluación de la recurrencia anterior lleva tiempo [matemático] O (nm) [/ matemático]. Hay una manera simple de optimizar el cálculo a [matemáticas] O (n) [/ matemáticas], lo dejaré como un ejercicio para el lector 🙂

Answer 2

No estoy tan seguro si entiendo el problema por completo. ¿No debería ser la respuesta en el ejemplo 11? Si estamos dividiendo 5 en como máximo 3 enteros, entonces

5 = 5 = 1 + 4 = 4 + 1 = 2 + 3 = 3 + 2 = 1 + 1 + 3 = 1 + 3 + 1 = 3 + 1 + 1 = 1 + 2 + 2 = 2 + 1 + 2 = 2 + 2 + 1

Entonces hay 11 formas posibles.

Si esto es lo que pretendía, una forma posible de resolver este problema es escribir un programa de programación dinámica de arriba hacia abajo (es decir, memorización).

// por Luke Kim
#include
#include
#include
#include
usando el espacio de nombres estándar;

#define MAXN 51
#define MAXK 51

caché int [MAXN] [MAXK];
int resolver (int n, int k) {
si (k <0) devuelve 0;
if (n == 0 && k> = 0) devuelve 1;
int & ret = caché [n] [k];
if (ret! = -1) devuelve ret;
ret = 0;
para (int i = 1; i <= n; i ++) {
if (ni> = 0) ret + = resolver (ni, k-1);
}
volver ret;
}

int main () {
ios_base :: sync_with_stdio (falso);
cin.tie (NULL);
int n, k; // el número a particionar, número máximo de particiones
cin >> n >> k;
memset (caché, -1, sizeof (caché));
cout << resolver (n, k) << endl;
devuelve 0;
}

Answer 3

Pensar en una función

countPartitions (int N, int max)

para encontrar el resultado intente todas las posiciones de 1 a N para dividir la secuencia en dos mitades. Desea max = a a la izquierda y max = b a la derecha, de modo que a + b + 1 = max.

Answer 4

Si no necesita usar la Programación dinámica, puede usar mi programa C (basado en un algoritmo de Donald Knuth).

http://gcrhoads.byethost4.com/Co …