part[i][j] es verdadera si es posible lograr una suma de i usando los primeros elementos j de la matriz y falsa en caso contrario. Si la part[i][j-1] es verdadera, se deduce que la part[i][j] también debe ser verdadera ya que si puede hacer la suma usando los primeros elementos j-1, puede hacer la suma usando la primera j elementos simplemente ignorando el último elemento y usando la misma suma que antes.
Ahora suponga que la part[i][j-1] es falsa. Todavía puede ser posible hacer la suma, pero en este caso se ve obligado a usar el elemento j-1 y queda por hacer una suma de i - arr[j-1] usando los primeros elementos j-1. Entonces, la part[i-arr[j-1]][j-1] debe ser verdadera, pero esto siempre será falsa si arr[j-1] > i ya que una suma negativa es imposible. Peor aún, intentará acceder a un elemento de matriz que esté fuera de los límites, de ahí el uso de la declaración de protección if.
Personalmente, creo que es un poco más claro reemplazar el código en el bucle for más interno con el único revestimiento:
- Dada una lista de conjuntos de 2 números, ¿cómo divide esta lista por la mitad de modo que la suma de cada uno de los números 1 y 2 para ambas mitades sea aproximadamente par?
- Cómo identificar problemas del mundo real que podemos resolver mediante el uso de la informática y las matemáticas
- ¿Practicar las matemáticas es bueno para la programación competitiva?
- Cómo resolver sumas consecutivas de UVa 12355
- Cómo mostrar que para cada número entero n, n> 0, el número entero (9 ^ n) -1 es divisible por 8
parte [i] [j] = parte [i] [j-1] || (arr [j-1]> i && parte [i-arr [j-1]] [j-1])
