Java - suma máxima en camino a través de una matriz 2D

Question

Básicamente tengo un problema que va algo similar a esto:

Hay un jardín de plantas de fresa representados por una 2D, matriz cuadrada. Cada planta (cada elemento) tiene varias fresas. Empiezas en la esquina superior izquierda de la matriz y solo puedes mover hacia la derecha o hacia abajo. Necesito diseñar un método recursivo para calcular los caminos a través del jardín y luego dar salida a cuál produce la mayor cantidad de fresas.

Creo que tengo una comprensión de los problemas de recursión realmente muy simples, pero este problema se me ha pasado por la cabeza. No estoy seguro de dónde empezar o dónde ir en lo que respecta a la creación de un método recursivo.

Cualquier ayuda relacionada con el código o que me ayude a comprender el concepto detrás de este problema es muy apreciada. Gracias.

Answer 1

Como dijo dasblinkenlight, la forma más eficiente de hacer esto es usando una técnica de memorización o programación dinámica. Tiendo a preferir la programación dinámica, pero usaré la recursión pura aquí.

La respuesta se centra alrededor de la respuesta a una pregunta fundamental: "Si estoy en el cuadrado de la fila ry la columna c de mi campo, ¿cómo puedo evaluar el camino desde la parte superior izquierda hasta aquí de modo que el número de las fresas están maximizadas? "

La clave para darse cuenta es que solo hay dos maneras de entrar en la parcela r y la columna c: o puedo llegar desde arriba, usando la gráfica en la fila r-1 y la columna c, o puedo obtener allí desde el lado, usando la trama en la fila r y la columna c-1. Después de eso, sólo tiene que asegurarse de que conoce sus casos base ... lo que significa, fundamentalmente, mi versión puramente recursiva sería algo así como:

int[][] field;  
int max(int r, int c) { 
    //Base case 
    if (r == 0 && c == 0) { 
     return field[r][c]; 
    } 
    //Assuming a positive number of strawberries in each plot, otherwise this needs 
    //to be negative infinity 
    int maxTop = -1, maxLeft = -1; 
    //We can't come from the top if we're in the top row 
    if (r != 0) { 
     maxTop = field[r-1][c]; 
    } 
    //Similarly, we can't come from the left if we're in the left column 
    if (c != 0) { 
     maxLeft = field[r][c-1]; 
    } 
    //Take whichever gives you more and return.. 
    return Math.max(maxTop, maxLeft) + field[r][c]; 
} 

llamada max (r-1, c-1) a consigue tu respuesta Observe que hay mucha ineficiencia aquí; lo hará mucho mejor utilizando la programación dinámica (que proporcionaré a continuación) o la memorización (que ya se ha definido). Sin embargo, lo que hay que recordar es que tanto las técnicas de DP como las de memorización son simplemente formas más eficientes que provienen de los principios recursivos utilizados aquí.

DP:

int maxValue(int[][] field) { 
    int r = field.length; 
    int c = field[0].length; 
    int[][] maxValues = new int[r][c]; 
    for (int i = 0; i < r; i++) { 
     for (int j = 0; j < c; j++) { 
      if (i == 0 && j == 0) { 
       maxValues[i][j] = field[i][j]; 
      } else if (i == 0) { 
       maxValues[i][j] = maxValues[i][j-1] + field[i][j]; 
      } else if (j == 0) { 
       maxValues[i][j] = maxValues[i-1][j] + field[i][j]; 
      } else { 
       maxValues[i][j] = Math.max(maxValues[i][j-1], maxValues[i-1][j]) + field[i][j]; 
      } 
     } 
    } 
    return maxValues[r-1][c-1]; 
} 

En ambos casos, si desea volver a crear la ruta real, sólo mantener una tabla 2D de booleanos que se corresponde con "¿Vine desde arriba o hacia la izquierda"? Si la mayor parte del camino de la fresa proviene de arriba, ponlo verdadero, de lo contrario ponlo falso. Eso puede permitirle volver a trazar el parche después del cálculo.

Tenga en cuenta que esto sigue siendo recursivo en el principio: en cada paso, estamos mirando hacia atrás en nuestros resultados anteriores. Simplemente, almacenamos en caché nuestros resultados anteriores para no perder mucho trabajo, y estamos atacando los subproblemas en un orden inteligente para que siempre podamos resolverlos. Para más sobre programación dinámica, vea Wikipedia.

Answer 2

Puede hacerlo usando memoization. Aquí se supone pseudodoce similar a Java (memo, R y C se supone que son variables de instancia disponibles para el método max).

int R = 10, C = 20; 
int memo[][] = new int[R][C]; 
for (int r=0 ; r != R ; r++) 
    for (int c = 0 ; c != C ; c++) 
     memo[r][c] = -1; 
int res = max(0, 0, field); 

int max(int r, int c, int[][] field) { 
    if (memo[r][c] != -1) return memo[r][c]; 
    int down = 0; right = 0; 
    if (r != R) down = max(r+1, c, field); 
    if (c != C) right = max(r, c+1, field); 
    return memo[r][c] = (field[r][c] + Math.max(down, right)); 
} 

Answer 3

Puede resolver esto con el método de tabulación DP, con el cual puede ahorrar espacio de O (m * n) a solo O (n). Con la memorización DP, necesita una matriz m * n para almacenar valores intermedios. A continuación está mi código Python. Espero que pueda ayudar.

def max_path(field): 
    dp = [sum(field[0][:i]) for i in range(1, len(field[0]) + 1)] 
    for i in range(1, len(field)): 
     for j in range(len(dp)): 
      dp[j] = min(dp[j], dp[j - 1] if j > 0 else float('inf')) + field[i][j] 
    return dp[-1]