# TDA | Ejercicio 9 practica 1
## Consigna
- Hay un terreno, que podemos pensarlo como una grilla de $m$ filas y $n$ columnas, con trampas y pociones. Queremos llegar de la esquina superior izquierda hasta la inferior derecha, y desde cada casilla solo podemos movernos a la casilla de la derecha o a la de abajo. Cada casilla $i,j$ tiene un número entero $A_{i,j}$ que nos modificará el nivel de vida sumándonos el número $A_{i,j}$ (si es negativo, nos va a restar $|A_{i,j}|$ de vida). Queremos saber el mínimo nivel de vida con el que debemos comenzar tal que haya un camino posible de modo que en todo momento nuestro nivel de vida sea al menos 1. Por ejemplo, si tenemos la grilla:
- $A$ =
[
[-2 -3 3]
[-5 -10 1]
[10 30 -5]
]
- el mínimo nivel de vida con el que podemos comenzar es 7 porque podemos realizar el camino que va todo a la derecha y todo abajo.
a) Pensar la idea de un algoritmo de backtracking (no hace falta escribirlo).
b) Convencerse de que, excepto que estemos en los límites del terreno, la mínima vida necesaria al llegar a la posición $i, j$ es el resultado de restar al mínimo entre la mínima vida necesaria en $i + 1, j$ y aquella en $i, j + 1$, el valor $A_{i,j}$, salvo que eso fuera menor o igual que 0, en cuyo caso sería 1.
c) Escribir una formulación recursiva basada en b). Explicar su semántica e indicar cuáles serían los parámetros para resolver el problema.
d) Diseñar un algoritmo de PD y dar su complejidad temporal y espacial auxiliar. Comparar cómo resultaría un enfoque top-down con uno bottom-up.
e) Dar un algoritmo bottom-up cuya complejidad temporal sea $O(m \cdot n)$ y la espacial auxiliar sea $O(\min(m,n))$.
## Resolución
## a)
- Podemos revisar todas las posibilidades de camino más optimo, sea sea por $A_{00}$, $A_{01}$ , ... $A_{|i|-1 , |j| - 1}$ o sea al revés.
- Lo que qiuero decir es que ya sea primero moviendose por oclumna y/o fila en cada rama de BT, me tiene que decir en que vida queda.
- Entonces podemos retornar el minimo de los diferentes llamados recursivos y retornar este numero pero en positivo y con un +1.
- En el ejemplo busca el minimo con una recursion que la suma da -6, le suma 6+1
## b)
- mi sobre-explicación en el inciso anteroir demuestra que el preconocimiento de lo que se explaya. Por lo tanto esta explicación queda evidente.
## c)
\begin{equation}
TV(M, i, j) =
\begin{cases}
1 & \text{si } M_{i,j} \geq 0 \\
\max\left(1, \min(TV(M, i+1, j), TV(M, i, j+1)) - M_{i,j}\right) & \text{en caso contrario}
\end{cases}
\end{equation}
- Los parametros de entrdada serian M, siendo M nuestra matriz de $n \times m$ columnas
- Lo que hace la función recursiva está explicado en el inciso a)
## d)
```python
memo = {} ## Pensar que tal vez conviene matriz
def tv(M:list[list[int]],i:int,j:int, memo=None):
if memo is None:
memo = {}
# Caso base intenta mantenerse en los limites de la matriz.
if i >= len(M) or j >= len(M[0]) or i < 0 or j < 0:
return float('inf') # Retornamos infinito para indicar que no es un camino válido
# Caso Base
if i == len(M) - 1 and j == len(M[0]) - 1: # Llegamos al final
return max(1, 1 - M[i][j])
if (i, j) in memo: # Verificamos si el resultado ya está memoizado
return memo[(i, j)]
moverseAbajo = tv(M,i+1,j, memo)
moverseDerecha = tv(M,i,j+1, memo)
memo[i,j] = max(1, min(moverseAbajo,moverseDerecha) - M[i][j])
return memo[(i,j)]
# Definición de la matriz M
M = [
[-2, -3, 3],
[-5, -10, 1],
[10, 30, -5]
]
# Llamamos a la función tv pasando la matriz y las coordenadas iniciales (0, 0)
resultado = tv(M, 0, 0)
# Imprimimos el resultado
print(f"El nivel mínimo de vida necesario para sobrevivir es: {resultado}")```