Dada una array donde cada celda representa puntos. ¿Cómo acumular el máximo de puntos usando dos recorridos en las siguientes condiciones?
Sean las dimensiones de la cuadrícula dada R x C.
- El primer recorrido comienza desde la esquina superior izquierda, es decir, (0, 0) y debe llegar a la esquina inferior izquierda, es decir, (R-1, 0). El segundo recorrido comienza desde la esquina superior derecha, es decir, (0, C-1) y debe llegar a la esquina inferior derecha, es decir, (R-1, C-1)/
- Desde un punto (i, j), podemos movernos a (i+1, j+1) o (i+1, j-1) o (i+1, j)
- Un recorrido obtiene todos los puntos de una celda particular a través de la cual pasa. Si un recorrido ya ha acumulado puntos de una celda, entonces el otro recorrido no obtiene puntos si vuelve a pasar por esa celda.
Input :
int arr[R][C] = {{3, 6, 8, 2},
{5, 2, 4, 3},
{1, 1, 20, 10},
{1, 1, 20, 10},
{1, 1, 20, 10},
};
Output: 73
Explanation :
First traversal collects total points of value 3 + 2 + 20 + 1 + 1 = 27
Second traversal collects total points of value 2 + 4 + 10 + 20 + 10 = 46.
Total Points collected = 27 + 46 = 73.
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
La idea es hacer ambos recorridos al mismo tiempo. Empezamos primero desde (0, 0) y el segundo recorrido desde (0, C-1) simultáneamente. Lo importante a tener en cuenta es que, en cualquier paso en particular, ambos recorridos estarán en la misma fila, ya que en los tres movimientos posibles, el número de fila aumenta. Sean (x1, y1) y (x2, y2) las posiciones actuales del primer y segundo recorrido respectivamente. Por lo tanto, en cualquier momento x1 será igual a x2 ya que ambos avanzan, pero es posible la variación a lo largo de y. Dado que la variación en y podría ocurrir de 3 maneras sin cambios (y), ve a la izquierda (y – 1), ve a la derecha (y + 1). Así que en total son posibles 9 combinaciones entre y1, y2. Los 9 casos que se mencionan a continuación después de los casos base.
Both traversals always move forward along x
Base Cases:
// If destinations reached
if (x == R-1 && y1 == 0 && y2 == C-1)
maxPoints(arr, x, y1, y2) = arr[x][y1] + arr[x][y2];
// If any of the two locations is invalid (going out of grid)
if input is not valid
maxPoints(arr, x, y1, y2) = -INF (minus infinite)
// If both traversals are at same cell, then we count the value of cell
// only once.
If y1 and y2 are same
result = arr[x][y1]
Else
result = arr[x][y1] + arr[x][y2]
result += max { // Max of 9 cases
maxPoints(arr, x+1, y1+1, y2),
maxPoints(arr, x+1, y1+1, y2+1),
maxPoints(arr, x+1, y1+1, y2-1),
maxPoints(arr, x+1, y1-1, y2),
maxPoints(arr, x+1, y1-1, y2+1),
maxPoints(arr, x+1, y1-1, y2-1),
maxPoints(arr, x+1, y1, y2),
maxPoints(arr, x+1, y1, y2+1),
maxPoints(arr, x+1, y1, y2-1)
}
La solución recursiva anterior tiene muchos subproblemas que se resuelven una y otra vez. Por lo tanto, podemos usar la programación dinámica para resolver el problema anterior de manera más eficiente. A continuación se muestra la implementación basada en la memorización (la memorización es una alternativa a la solución iterativa basada en tablas en la programación dinámica). En la implementación a continuación, usamos una tabla de memorización ‘mem’ para realizar un seguimiento de los problemas ya resueltos.
C++
// A Memoization based program to find maximum collection
// using two traversals of a grid
#include<bits/stdc++.h>
using namespace std;
#define R 5
#define C 4
// checks whether a given input is valid or not
bool isValid(int x, int y1, int y2)
{
return (x >= 0 && x < R && y1 >=0 &&
y1 < C && y2 >=0 && y2 < C);
}
// Driver function to collect max value
int getMaxUtil(int arr[R][C], int mem[R][C][C], int x, int y1, int y2)
{
/*---------- BASE CASES -----------*/
// if P1 or P2 is at an invalid cell
if (!isValid(x, y1, y2)) return INT_MIN;
// if both traversals reach their destinations
if (x == R-1 && y1 == 0 && y2 == C-1)
return (y1 == y2)? arr[x][y1]: arr[x][y1] + arr[x][y2];
// If both traversals are at last row but not at their destination
if (x == R-1) return INT_MIN;
// If subproblem is already solved
if (mem[x][y1][y2] != -1) return mem[x][y1][y2];
// Initialize answer for this subproblem
int ans = INT_MIN;
// this variable is used to store gain of current cell(s)
int temp = (y1 == y2)? arr[x][y1]: arr[x][y1] + arr[x][y2];
/* Recur for all possible cases, then store and return the
one with max value */
ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1, y2-1));
ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1, y2+1));
ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1, y2));
ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1-1, y2));
ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1-1, y2-1));
ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1-1, y2+1));
ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1+1, y2));
ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1+1, y2-1));
ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1+1, y2+1));
return (mem[x][y1][y2] = ans);
}
// This is mainly a wrapper over recursive function getMaxUtil().
// This function creates a table for memoization and calls
// getMaxUtil()
int geMaxCollection(int arr[R][C])
{
// Create a memoization table and initialize all entries as -1
int mem[R][C][C];
memset(mem, -1, sizeof(mem));
// Calculation maximum value using memoization based function
// getMaxUtil()
return getMaxUtil(arr, mem, 0, 0, C-1);
}
// Driver program to test above functions
int main()
{
int arr[R][C] = {{3, 6, 8, 2},
{5, 2, 4, 3},
{1, 1, 20, 10},
{1, 1, 20, 10},
{1, 1, 20, 10},
};
cout << "Maximum collection is " << geMaxCollection(arr);
return 0;
}
Java
// A Memoization based program to find maximum collection
// using two traversals of a grid
class GFG
{
static final int R = 5;
static final int C = 4;
// checks whether a given input is valid or not
static boolean isValid(int x, int y1, int y2)
{
return (x >= 0 && x < R && y1 >=0 &&
y1 < C && y2 >=0 && y2 < C);
}
// Driver function to collect Math.max value
static int getMaxUtil(int arr[][], int mem[][][],
int x, int y1, int y2)
{
/*---------- BASE CASES -----------*/
// if P1 or P2 is at an invalid cell
if (!isValid(x, y1, y2)) return Integer.MIN_VALUE;
// if both traversals reach their destinations
if (x == R-1 && y1 == 0 && y2 == C-1)
return (y1 == y2)? arr[x][y1]: arr[x][y1] + arr[x][y2];
// If both traversals are at last
// row but not at their destination
if (x == R-1) return Integer.MIN_VALUE;
// If subproblem is already solved
if (mem[x][y1][y2] != -1) return mem[x][y1][y2];
// Initialize answer for this subproblem
int ans = Integer.MIN_VALUE;
// this variable is used to store
// gain of current cell(s)
int temp = (y1 == y2)? arr[x][y1]:
arr[x][y1] + arr[x][y2];
/* Recur for all possible cases, then store
and return the one with max value */
ans = Math.max(ans, temp +
getMaxUtil(arr, mem, x+1, y1, y2-1));
ans = Math.max(ans, temp +
getMaxUtil(arr, mem, x+1, y1, y2+1));
ans = Math.max(ans, temp +
getMaxUtil(arr, mem, x+1, y1, y2));
ans = Math.max(ans, temp +
getMaxUtil(arr, mem, x+1, y1-1, y2));
ans = Math.max(ans, temp +
getMaxUtil(arr, mem, x+1, y1-1, y2-1));
ans = Math.max(ans, temp +
getMaxUtil(arr, mem, x+1, y1-1, y2+1));
ans = Math.max(ans, temp +
getMaxUtil(arr, mem, x+1, y1+1, y2));
ans = Math.max(ans, temp +
getMaxUtil(arr, mem, x+1, y1+1, y2-1));
ans = Math.max(ans, temp +
getMaxUtil(arr, mem, x+1, y1+1, y2+1));
return (mem[x][y1][y2] = ans);
}
// This is mainly a wrapper over recursive
// function getMaxUtil(). This function
// creates a table for memoization and
// calls getMaxUtil()
static int geMaxCollection(int arr[][])
{
// Create a memoization table and
// initialize all entries as -1
int [][][]mem = new int[R][C][C];
for(int i = 0; i < R; i++)
{
for(int j = 0; j < C; j++)
{
for(int l = 0; l < C; l++)
mem[i][j][l]=-1;
}
}
// Calculation maximum value using memoization
// based function getMaxUtil()
return getMaxUtil(arr, mem, 0, 0, C-1);
}
// Driver code
public static void main(String[] args)
{
int arr[][] = {{3, 6, 8, 2},
{5, 2, 4, 3},
{1, 1, 20, 10},
{1, 1, 20, 10},
{1, 1, 20, 10},
};
System.out.print("Maximum collection is " +
geMaxCollection(arr));
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# A Memoization based program to find maximum collection
# using two traversals of a grid
R=5
C=4
intmin=-10000000
intmax=10000000
# checks whether a given input is valid or not
def isValid(x,y1,y2):
return ((x >= 0 and x < R and y1 >=0
and y1 < C and y2 >=0 and y2 < C))
# Driver function to collect max value
def getMaxUtil(arr,mem,x,y1,y2):
# ---------- BASE CASES -----------
if isValid(x, y1, y2)==False:
return intmin
# if both traversals reach their destinations
if x == R-1 and y1 == 0 and y2 == C-1:
if y1==y2:
return arr[x][y1]
else:
return arr[x][y1]+arr[x][y2]
# If both traversals are at last row
# but not at their destination
if x==R-1:
return intmin
# If subproblem is already solved
if mem[x][y1][y2] != -1:
return mem[x][y1][y2]
# Initialize answer for this subproblem
ans=intmin
# this variable is used to store gain of current cell(s)
temp=0
if y1==y2:
temp=arr[x][y1]
else:
temp=arr[x][y1]+arr[x][y2]
# Recur for all possible cases, then store and return the
# one with max value
ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1, y2-1))
ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1, y2+1))
ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1, y2))
ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1-1, y2))
ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1-1, y2-1))
ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1-1, y2+1))
ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1+1, y2))
ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1+1, y2-1))
ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1+1, y2+1))
mem[x][y1][y2] = ans
return ans
# This is mainly a wrapper over recursive
# function getMaxUtil().
# This function creates a table for memoization and calls
# getMaxUtil()
def geMaxCollection(arr):
# Create a memoization table and
# initialize all entries as -1
mem=[[[-1 for i in range(C)] for i in range(C)] for i in range(R)]
# Calculation maximum value using
# memoization based function
# getMaxUtil()
return getMaxUtil(arr, mem, 0, 0, C-1)
# Driver program to test above functions
if __name__=='__main__':
arr=[[3, 6, 8, 2],
[5, 2, 4, 3],
[1, 1, 20, 10],
[1, 1, 20, 10],
[1, 1, 20, 10],
]
print('Maximum collection is ', geMaxCollection(arr))
#this code is contributed by sahilshelangia
C#
// A Memoization based program to find maximum collection
// using two traversals of a grid
using System;
class GFG
{
static readonly int R = 5;
static readonly int C = 4;
// checks whether a given input is valid or not
static bool isValid(int x, int y1, int y2)
{
return (x >= 0 && x < R && y1 >=0 &&
y1 < C && y2 >=0 && y2 < C);
}
// Driver function to collect Math.max value
static int getMaxUtil(int [,]arr, int [,,]mem,
int x, int y1, int y2)
{
/*---------- BASE CASES -----------*/
// if P1 or P2 is at an invalid cell
if (!isValid(x, y1, y2)) return int.MinValue;
// if both traversals reach their destinations
if (x == R-1 && y1 == 0 && y2 == C-1)
return (y1 == y2)? arr[x, y1]: arr[x, y1] + arr[x, y2];
// If both traversals are at last
// row but not at their destination
if (x == R-1) return int.MinValue;
// If subproblem is already solved
if (mem[x, y1, y2] != -1) return mem[x, y1, y2];
// Initialize answer for this subproblem
int ans = int.MinValue;
// this variable is used to store
// gain of current cell(s)
int temp = (y1 == y2)? arr[x, y1]:
arr[x, y1] + arr[x, y2];
/* Recur for all possible cases, then store
and return the one with max value */
ans = Math.Max(ans, temp +
getMaxUtil(arr, mem, x+1, y1, y2-1));
ans = Math.Max(ans, temp +
getMaxUtil(arr, mem, x+1, y1, y2+1));
ans = Math.Max(ans, temp +
getMaxUtil(arr, mem, x+1, y1, y2));
ans = Math.Max(ans, temp +
getMaxUtil(arr, mem, x+1, y1-1, y2));
ans = Math.Max(ans, temp +
getMaxUtil(arr, mem, x+1, y1-1, y2-1));
ans = Math.Max(ans, temp +
getMaxUtil(arr, mem, x+1, y1-1, y2+1));
ans = Math.Max(ans, temp +
getMaxUtil(arr, mem, x+1, y1+1, y2));
ans = Math.Max(ans, temp +
getMaxUtil(arr, mem, x+1, y1+1, y2-1));
ans = Math.Max(ans, temp +
getMaxUtil(arr, mem, x+1, y1+1, y2+1));
return (mem[x, y1, y2] = ans);
}
// This is mainly a wrapper over recursive
// function getMaxUtil(). This function
// creates a table for memoization and
// calls getMaxUtil()
static int geMaxCollection(int [,]arr)
{
// Create a memoization table and
// initialize all entries as -1
int [,,]mem = new int[R, C, C];
for(int i = 0; i < R; i++)
{
for(int j = 0; j < C; j++)
{
for(int l = 0; l < C; l++)
mem[i, j, l]=-1;
}
}
// Calculation maximum value using memoization
// based function getMaxUtil()
return getMaxUtil(arr, mem, 0, 0, C-1);
}
// Driver code
public static void Main(String[] args)
{
int [,]arr = {{3, 6, 8, 2},
{5, 2, 4, 3},
{1, 1, 20, 10},
{1, 1, 20, 10},
{1, 1, 20, 10},
};
Console.Write("Maximum collection is " +
geMaxCollection(arr));
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// A Memoization based program to find maximum collection
// using two traversals of a grid
var R = 5;
var C = 4;
// checks whether a given input is valid or not
function isValid(x , y1 , y2)
{
return (x >= 0 && x < R && y1 >=0 &&
y1 < C && y2 >=0 && y2 < C);
}
// Driver function to collect Math.max value
function getMaxUtil(arr , mem,
x , y1 , y2)
{
/*---------- BASE CASES -----------*/
// if P1 or P2 is at an invalid cell
if (!isValid(x, y1, y2)) return Number.MIN_VALUE;
// if both traversals reach their destinations
if (x == R-1 && y1 == 0 && y2 == C-1)
return (y1 == y2)? arr[x][y1]: arr[x][y1] + arr[x][y2];
// If both traversals are at last
// row but not at their destination
if (x == R-1) return Number.MIN_VALUE;
// If subproblem is already solved
if (mem[x][y1][y2] != -1) return mem[x][y1][y2];
// Initialize answer for this subproblem
var ans = Number.MIN_VALUE;
// this variable is used to store
// gain of current cell(s)
var temp = (y1 == y2)? arr[x][y1]:
arr[x][y1] + arr[x][y2];
/* Recur for all possible cases, then store
and return the one with max value */
ans = Math.max(ans, temp +
getMaxUtil(arr, mem, x+1, y1, y2-1));
ans = Math.max(ans, temp +
getMaxUtil(arr, mem, x+1, y1, y2+1));
ans = Math.max(ans, temp +
getMaxUtil(arr, mem, x+1, y1, y2));
ans = Math.max(ans, temp +
getMaxUtil(arr, mem, x+1, y1-1, y2));
ans = Math.max(ans, temp +
getMaxUtil(arr, mem, x+1, y1-1, y2-1));
ans = Math.max(ans, temp +
getMaxUtil(arr, mem, x+1, y1-1, y2+1));
ans = Math.max(ans, temp +
getMaxUtil(arr, mem, x+1, y1+1, y2));
ans = Math.max(ans, temp +
getMaxUtil(arr, mem, x+1, y1+1, y2-1));
ans = Math.max(ans, temp +
getMaxUtil(arr, mem, x+1, y1+1, y2+1));
return (mem[x][y1][y2] = ans);
}
// This is mainly a wrapper over recursive
// function getMaxUtil(). This function
// creates a table for memoization and
// calls getMaxUtil()
function geMaxCollection(arr)
{
// Create a memoization table and
// initialize all entries as -1
var mem = Array(R).fill().map(()=>Array(C).fill().map(()=>Array(C).fill(0)));
for(i = 0; i < R; i++)
{
for(j = 0; j < C; j++)
{
for(l = 0; l < C; l++)
mem[i][j][l]=-1;
}
}
// Calculation maximum value using memoization
// based function getMaxUtil()
return getMaxUtil(arr, mem, 0, 0, C-1);
}
// Driver code
var arr = [[3, 6, 8, 2],
[5, 2, 4, 3],
[1, 1, 20, 10],
[1, 1, 20, 10],
[1, 1, 20, 10],
];
document.write("Maximum collection is " +
geMaxCollection(arr));
// This code is contributed by aashish1995
</script>
Producción
Maximum collection is 73
Complejidad temporal: O(R x C x C).
Espacio Auxiliar: O(R x C x C).
Gracias a Aarti_Rathi y Gaurav Ahirwar por sugerir el problema y la solución anteriores.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA