Link del problema: 1079 - Sums In a Triangle I
Dificultad: Fácil
Problema: Dado un número $N$ donde $1<=N<=100$ se tienen $N$ niveles en un triangulo, así el primer nivel tiene 1 número, el segundo nivel tiene 2 números, el tercero 3, etc. El programa debe encontrar la máxima suma desde el primer nivel hasta el último pudiendo tomar una ruta tal que solo se acceda al número de abajo o al de abajo y una posición a la derecha...
Ejemplo:
Con $N = 3 $
Tenemos el siguiente triángulo:
1
1 2
2 3 1
Con $N = 3 $
Tenemos el siguiente triángulo:
1
1 2
2 3 1
La respuesta es 6 ya que primero solo tomamos el primer elemento pues no hay más opción ya que es el único elemento en la fila en la siguiente podemos tomar el 1 o 2
1
1 2 //La mejor opción aquí es tomar el de abajo y a la derecha que es el mayor
1 2 //La mejor opción aquí es tomar el de abajo y a la derecha que es el mayor
2 3 1
Hasta este punto llevamos la "mejor" ruta posible habiendo tomado los elementos de mayor prioridad entonces en la siguiente iteración solo podemos tomar dos elementos:
1
1 2
1 2
2 3 1 //La mejor opción aquí es tomar el de abajo que es el mayor
Y así por fin llegar a nuestro cometido que era tomar la ruta tal que la suma sea la mayor...
Y así por fin llegar a nuestro cometido que era tomar la ruta tal que la suma sea la mayor...
Solución: (DP)
Este problema se resuelve con Programación Dinámica (DP) ya que tenemos que tomar una decisión en cada nivel (la mejor) y así ir tomar la mejor ruta que podamos, entonces como se mencionó en nuestra otra publicación de DP tenemos que establecer los ESTADOS de la DP y las DECISIONES para lo cual nuestros estados tendremos:
int dp(int i,int j){
}
Necesitaremos un apuntador a la columna donde estemos (i) y uno para la fila (j) para saber en que número vamos.
Lo siguiente es establecer donde se tendrá que detener la DP así que necesitamos un caso base para la recursión. Para lo cual:
if(i==n) return 0;
Vemos que si nuestro apuntador llega a la última columna tendremos que detener la DP.
Por último necesitamos nuestras decisiones, aquí solo basta con devolver el MÁXIMO entre tomar el de abajo dp(i+1,j) y tomar el de abajo y una posición a la derecha dp(i+1,j+1) y sumar en cada decisión el elemento que corresponde a esa posición de la siguiente manera:
return max(dp(i+1,j)+piramide[i+1][j],dp(i+1,j+1)+piramide[i+1][j+1]);
Y así se resolvería el problema, cabe decir que mis números los guarde en un arreglo llamado pirámide para así poder usarlos después y sumarlos. Ahora un punto IMPORTANTE al final a la respuesta que devuelva esta función tenemos que sumarle el primer elemento del triángulo ya que aquí NO estamos considerándolo.
res = dp(0,0);
printf("%d\n",res + piramide[0][0]);
Y bueno eso fue todo por esta ocasión, ya saben si gustan sugerir algún tema pueden hacerlo abiertamente y espero les haya gustado comenten si hay dudas y escriban.
Adrián Fernández @ferprogramming
Adrián Fernández @ferprogramming
No hay comentarios on "Sums in a Triangle I (COJ)"