Dada una array grid[][] de tamaño M * N donde cada celda de la array denota el costo de estar presente en esa celda. La tarea es maximizar el costo de moverse a la última fila desde la esquina superior izquierda y superior derecha de la array donde en cada paso:
- Desde la celda (i, j) puede haber un movimiento hacia (i+1, j-1) , (i+1, j) o (i+1, j+1) .
- Si ambos puntos están en la misma celda al mismo tiempo, el costo de la celda se agregará solo para uno.
- En ningún momento, los puntos pueden salir de la cuadrícula.
Ejemplos:
Entrada:
cuadrícula = {{3, 1, 1},
{2, 5, 1},
{1, 5, 5},
{2, 1, 1}}
Salida: 24
Explicación: ruta desde arriba a la izquierda y desde arriba derecha se describen en color naranja y azul respectivamente.
El costo del primer camino es (3 + 2 + 5 + 2) = 12.
El costo del segundo camino es (1 + 5 + 5 + 1) = 12.
El costo total es 12 + 12 = 24.
Ex1 – Cuadrícula visual
Entrada:
cuadrícula = {{1, 0, 0, 0, 0, 0, 1},
{2, 0, 0, 0, 0, 3, 0},
{2, 0, 9, 0, 0, 0, 0},
{0, 3, 0, 5, 4, 0, 0},
{1, 0, 2, 3, 0, 0, 6}}
Salida: 28
Explicación: la ruta desde la parte superior izquierda y la parte superior derecha son descritas en color naranja y azul respectivamente.
El costo del primer camino es (1 + 9 + 5 + 2) = 17. El
costo del segundo camino es (1 + 3 + 4 + 3) = 11. El
costo total de los caminos es 17 + 11 = 28.
Esto es el costo máximo posible.
Ex2 – Cuadrícula visual
Intuición: denote el punto en la esquina superior izquierda como point1 y en la esquina superior derecha como point2 . Lo que sigue es la intuición detrás de la solución del problema.
- Tenga en cuenta que el orden de sus movimientos no importa, ya que no afectaría el resultado final. El costo final depende de las pistas de los puntos. Por lo tanto, los movimientos pueden ser en cualquier orden. Es necesario aplicar DP , así que busque un orden que sea adecuado para DP . Pruebe aquí algunas posibles órdenes de mudanza.
¿Se puede mover el punto 1 primero a la fila inferior y luego el punto 2?
Tal vez no. En este caso, el movimiento del punto 1 afectará al movimiento del punto 2 . En otras palabras, la pista óptima del punto2 depende de la pista del punto1 . En este caso, será necesario registrar toda la pista del punto 1 como el estado del punto 2 en DP. El número de subproblemas es demasiado.
De hecho, en cualquier caso, cuando cualquier punto se mueve varios pasos antes que el otro, el movimiento del primer punto impactará el movimiento del otro punto. Entonces, ambos puntos deben moverse sincrónicamente.
- Defina el estado de DP como (fila1, columna1, fila2, columna2) , donde (fila1, columna1) representa la ubicación del punto1 y (fila2, columna2) representa la ubicación del punto2 . Si se mueven sincrónicamente, ambos puntos estarán siempre en la misma fila. Por lo tanto, fila1 = fila2 .
Sea fila = fila1 = fila2 . El estado de DP se simplifica a (fila, columna1, columna2) , donde (fila, columna1) representa la ubicación del punto1 y (fila, columna2) representa la ubicación del punto2 . - Entonces, para la función DP: Deje que dp(row, col1, col2) devuelva el costo máximo, si point1 comienza en (row, col1) y point2 comienza en (row, col2) .
- Los casos base son que ambos puntos comienzan en la línea inferior. En este caso, no es necesario moverse, solo se considera el costo en las celdas actuales. Recuerde no contar dos veces si los puntos están exactamente en la misma celda.
- En otros casos, agregue el costo máximo de las rutas en el futuro. Aquí viene la función de transición. Dado que los puntos se pueden mover sincrónicamente, y cada punto tiene tres movimientos diferentes para un paso, hay un total de 3*3 = 9 movimientos posibles para dos robots:
| SL. No. | movimiento Punto1 | Movimiento punto2 |
|---|---|---|
| 1 | Izquierda hacia abajo | Izquierda hacia abajo |
| 2 | Izquierda hacia abajo | Abajo |
| 3 | Izquierda hacia abajo | Justo abajo |
| 4 | Abajo | Izquierda hacia abajo |
| 5 | Abajo | Abajo |
| 6 | Abajo | Justo abajo |
| 7 | Justo abajo | Izquierda hacia abajo |
| 8 | Justo abajo | Abajo |
| 9 | Justo abajo | Justo abajo |
- El costo máximo de las rutas en el futuro sería el máximo de esos 9 movimientos, que es el máximo de
dp(row+1, new_col1, new_col2) , donde new_col1 puede ser col1 , col1+1 o col1-1 y new_col2 puede ser col2 , col2+1 o col2-1 .
Enfoque 1: programación dinámica (de abajo hacia arriba): la solución del problema se basa en el concepto de programación dinámica y utiliza la intuición anterior.
- Defina una función dp que tome tres filas enteras, col1 y col2 como entrada.
- (fila, columna1) representa la ubicación del punto1 y (fila, columna2) representa la ubicación del punto2 .
- La función dp devuelve el costo máximo si el punto1 comienza en (fila, columna1) y el punto2 comienza en (fila, columna2) .
- En la función dp :
- Agregue el costo en (fila, col1) y (fila, col2) . No cuente dos veces si col1 = col2 .
- Si no se llega a la última fila, agregue el costo máximo que se puede obtener en la ruta futura.
- El costo máximo que se puede lograr en el futuro es el máximo de dp(row+1, new_col1, new_col2) , donde new_col1 puede ser col1, col1+1 o col1-1 , y new_col2 puede ser col2, col2+1, o col2-1 .
- Devolver el costo total.
- Finalmente, devuelve dp(row=0, col1=0, col2=last_column) en la función principal.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Dp function
int dp(int row, int col1, int col2,
vector<vector<int> >& grid,
vector<vector<vector<int> > >& dpCache)
{
if (col1 < 0 || col1 >= grid[0].size()
|| col2 < 0 || col2 >= grid[0].size())
return 0;
// Check cache
if (dpCache[row][col1][col2] != -1)
return dpCache[row][col1][col2];
// Add cost of the current cell
int result = grid[row][col1];
if (col1 != col2)
result
+= grid[row][col2];
// DP transition
if (row != grid.size() - 1) {
int maximum = 0;
for (int newCol1 = col1 - 1;
newCol1 <= col1 + 1; newCol1++)
for (int newCol2 = col2 - 1;
newCol2 <= col2 + 1;
newCol2++)
maximum
= max(maximum,
dp(row + 1, newCol1,
newCol2, grid,
dpCache));
result += maximum;
}
dpCache[row][col1][col2] = result;
return result;
}
// Function to maximize the cost
int pickup(vector<vector<int> >& grid)
{
int M = grid.size();
if (M == 0)
return 0;
int N = grid[0].size();
if (N == 0)
return 0;
vector<vector<vector<int> > >
dpCache(M, vector<vector<int> >(
N, vector<int>(N, -1)));
return dp(0, 0, N - 1, grid, dpCache);
}
// Driver code
int main()
{
vector<vector<int> > grid{
{ 3, 1, 1 }, { 2, 5, 1 },
{ 1, 5, 5 }, { 2, 1, 1 }
};
cout << pickup(grid);
return 0;
}
Java
// Java code to implement the approach
import java.util.*;
class GFG{
static int[][] grid = {
{ 3, 1, 1 }, { 2, 5, 1 },
{ 1, 5, 5 }, { 2, 1, 1 }
};
static int[][][] dpCache;
// Dp function
static int dp(int row, int col1, int col2)
{
if (col1 < 0 || col1 >= grid[0].length
|| col2 < 0 || col2 >= grid[0].length)
return 0;
// Check cache
if (dpCache[row][col1][col2] != -1)
return dpCache[row][col1][col2];
// Add cost of the current cell
int result = grid[row][col1];
if (col1 != col2)
result
+= grid[row][col2];
// DP transition
if (row != grid.length - 1) {
int maximum = 0;
for (int newCol1 = col1 - 1;
newCol1 <= col1 + 1; newCol1++)
for (int newCol2 = col2 - 1;
newCol2 <= col2 + 1;
newCol2++)
maximum
= Math.max(maximum,
dp(row + 1, newCol1,
newCol2));
result += maximum;
}
dpCache[row][col1][col2] = result;
return result;
}
// Function to maximize the cost
static int pickup()
{
int M = grid.length;
if (M == 0)
return 0;
int N = grid[0].length;
if (N == 0)
return 0;
dpCache = new int[M][N][N];
for(int i = 0; i < M; i++)
{
for(int j = 0; j < N; j++)
{
for(int l = 0; l < N; l++)
dpCache[i][j][l] = -1;
}
}
return dp(0, 0, N - 1);
}
// Driver code
public static void main(String[] args)
{
System.out.print(pickup());
}
}
// This code is contributed by Rajput-Ji
Python3
# python3 code to implement the approach # Dp function def dp(row, col1, col2, grid, dpCache): if (col1 < 0 or col1 >= len(grid[0]) or col2 < 0 or col2 >= len(grid[0])): return 0 # Check cache if (dpCache[row][col1][col2] != -1): return dpCache[row][col1][col2] # Add cost of the current cell result = grid[row][col1] if (col1 != col2): result += grid[row][col2] # DP transition if (row != len(grid) - 1): maximum = 0 for newCol1 in range(col1-1, col1 + 2): for newCol2 in range(col2-1, col2+2): maximum = max(maximum, dp(row + 1, newCol1, newCol2, grid, dpCache)) result += maximum dpCache[row][col1][col2] = result return result # Function to maximize the cost def pickup(grid): M = len(grid) if (M == 0): return 0 N = len(grid[0]) if (N == 0): return 0 dpCache = [[[-1 for _ in range(N)] for _ in range(N)] for _ in range(M)] return dp(0, 0, N - 1, grid, dpCache) # Driver code if __name__ == "__main__": grid = [ [3, 1, 1], [2, 5, 1], [1, 5, 5], [2, 1, 1] ] print(pickup(grid)) # This code is contributed by rakeshsahni
C#
// C# code to implement the approach
using System;
public class GFG{
static int[,] grid = {
{ 3, 1, 1 }, { 2, 5, 1 },
{ 1, 5, 5 }, { 2, 1, 1 }
};
static int[,,] dpCache;
// Dp function
static int dp(int row, int col1, int col2)
{
if (col1 < 0 || col1 >= grid.GetLength(1)
|| col2 < 0 || col2 >= grid.GetLength(1))
return 0;
// Check cache
if (dpCache[row,col1,col2] != -1)
return dpCache[row,col1,col2];
// Add cost of the current cell
int result = grid[row,col1];
if (col1 != col2)
result
+= grid[row,col2];
// DP transition
if (row != grid.GetLength(0) - 1) {
int maximum = 0;
for (int newCol1 = col1 - 1;
newCol1 <= col1 + 1; newCol1++)
for (int newCol2 = col2 - 1;
newCol2 <= col2 + 1;
newCol2++)
maximum
= Math.Max(maximum,
dp(row + 1, newCol1,
newCol2));
result += maximum;
}
dpCache[row,col1,col2] = result;
return result;
}
// Function to maximize the cost
static int pickup()
{
int M = grid.GetLength(0);
if (M == 0)
return 0;
int N = grid.GetLength(1);
if (N == 0)
return 0;
dpCache = new int[M,N,N];
for(int i = 0; i < M; i++)
{
for(int j = 0; j < N; j++)
{
for(int l = 0; l < N; l++)
dpCache[i,j,l] = -1;
}
}
return dp(0, 0, N - 1);
}
// Driver code
public static void Main(String[] args)
{
Console.Write(pickup());
}
}
// This code contributed by shikhasingrajput
Javascript
<script>
// JavaScript code to implement the approach
// Dp function
function dp(row, col1, col2, grid, dpCache)
{
if (col1 < 0 || col1 >= grid[0].length
|| col2 < 0 || col2 >= grid[0].length)
return 0;
// Check cache
if (dpCache[row][col1][col2] != -1)
return dpCache[row][col1][col2];
// Add cost of the current cell
let result = grid[row][col1];
if (col1 != col2)
result
+= grid[row][col2];
// DP transition
if (row != grid.length - 1) {
let maximum = 0;
for (let newCol1 = col1 - 1;newCol1 <= col1 + 1; newCol1++){
for (let newCol2 = col2 - 1;newCol2 <= col2 + 1;newCol2++){
maximum = Math.max(maximum, dp(row + 1, newCol1, newCol2, grid, dpCache));
}
}
result += maximum;
}
dpCache[row][col1][col2] = result;
return result;
}
// Function to maximize the cost
function pickup(grid)
{
let M = grid.length;
if (M == 0)
return 0;
let N = grid[0].length;
if (N == 0)
return 0;
let dpCache = new Array(M);
for(let i = 0; i < M; i++)
{
dpCache[i] = new Array(N);
for(let j = 0; j < N; j++)
{
dpCache[i][j] = new Array(N).fill(-1);
}
}
return dp(0, 0, N - 1, grid, dpCache);
}
// Driver code
let grid = [[ 3, 1, 1 ], [ 2, 5, 1 ],
[ 1, 5, 5 ], [ 2, 1, 1 ]
];
document.write(pickup(grid));
// This code is contributed by shinjanpatra
</script>
Producción
24
Complejidad de Tiempo: O(M * N 2 )
Espacio Auxiliar: O(M * N 2 )
Enfoque 2: programación dinámica (de arriba hacia abajo): esta solución también se basa en el enfoque de programación dinámica que utiliza la intuición mencionada anteriormente. La única diferencia es que aquí se utiliza el enfoque de arriba hacia abajo .
- Defina una array dp tridimensional donde cada dimensión tenga un tamaño de M, N y N respectivamente, similar al enfoque 1.
- Aquí dp[fila][col1][col2] representa el costo máximo al llegar al punto 1 en (fila, columna 1) y al punto 2 en la posición (fila, columna 2) .
- Para calcular dp[row][col1][col2] (ecuación de transición):
- Agregue el costo en (fila, col1) y (fila, col2). No cuente dos veces si col1 = col2.
- Si no está en la primera fila, agregue el costo máximo de la ruta ya visitada.
- Finalmente, devuelva el valor máximo de la última fila.
Nota: la compresión de estado se puede usar para guardar la primera dimensión: dp[col1][col2] . Simplemente reutilice la array dp después de iterar una fila.
Implementación 1: sin compresión de estado
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to maximize the cost
int pickup(vector<vector<int> >& grid)
{
int M = grid.size();
if (M == 0)
return 0;
int N = grid[0].size();
if (N == 0)
return 0;
vector<vector<vector<int> > > dp(
M, vector<vector<int> >(
N, vector<int>(N, INT_MIN)));
dp[0][0][N - 1] = grid[0][0]
+ grid[0][N - 1];
for (int i = 1; i < M; i++)
for (int a = 0; a < N; a++)
for (int b = 0; b < N; b++)
for (int l = a - 1; l
<= a + 1;
l++)
for (int r = b - 1;
r <= b + 1; r++) {
if (l < 0 || l >= N
|| r < 0
|| r >= N)
continue;
dp[i][a][b] = max(
dp[i][a][b],
((a != b)
? grid[i][a]
+ grid[i][b]
: grid[i][a])
+ dp[i - 1][l][r]);
}
for (int i =0 ;i <M;i++)
for(int j =0 ;j < N;j++)
for (int k =0;k <N;k++)
cout<<dp[i][j][k]<<" ";
int ans = 0;
for (int a = 0; a < N; a++)
for (int b = 0; b < N; b++)
ans = max(ans, dp[M - 1][a][b]);
return ans;
}
// Driver code
int main()
{
vector<vector<int> > grid{
{ 3, 1, 1 }, { 2, 5, 1 },
{ 1, 5, 5 }, { 2, 1, 1 }
};
cout << pickup(grid);
return 0;
}
Java
import java.util.*;
import java.io.*;
// Java program for the above approach
class GFG{
// Function to maximize the cost
public static int pickup(ArrayList<ArrayList<Integer>> grid)
{
int M = grid.size();
if (M == 0){
return 0;
}
int N = grid.get(0).size();
if (N == 0){
return 0;
}
ArrayList<ArrayList<ArrayList<Integer>>> dp = new ArrayList<ArrayList<ArrayList<Integer>>>();
// Initializing dp arraylist
for(int i = 0 ; i < M ; i++){
ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>();
for(int j = 0 ; j < N ; j++){
ArrayList<Integer> temp1 = new ArrayList<Integer>();
for(int k = 0 ; k < N ; k++){
temp1.add(Integer.MIN_VALUE);
}
temp.add(temp1);
}
dp.add(temp);
}
dp.get(0).get(0).set(N - 1, grid.get(0).get(0) + grid.get(0).get(N - 1));
for (int i = 1; i < M; i++){
for (int a = 0; a < N; a++){
for (int b = 0; b < N; b++){
for (int l = a - 1; l <= a + 1; l++){
for (int r = b - 1; r <= b + 1; r++) {
if (l < 0 || l >= N || r < 0 || r >= N)
continue;
dp.get(i).get(a).set(b, Math.max(dp.get(i).get(a).get(b), ((a != b) ? grid.get(i).get(a) + grid.get(i).get(b) : grid.get(i).get(a)) + dp.get(i-1).get(l).get(r)));
}
}
}
}
}
int ans = 0;
for (int a = 0 ; a < N ; a++){
for (int b = 0 ; b < N ; b++){
ans = Math.max(ans, dp.get(M - 1).get(a).get(b));
}
}
return ans;
}
// Driver code
public static void main(String args[])
{
ArrayList<ArrayList<Integer>> grid = new ArrayList<ArrayList<Integer>>(
List.of(
new ArrayList<Integer>(
List.of(3, 1, 1)
),
new ArrayList<Integer>(
List.of(2, 5, 1)
),
new ArrayList<Integer>(
List.of(1, 5, 5)
),
new ArrayList<Integer>(
List.of(2, 1, 1)
)
)
);
System.out.println(pickup(grid));
}
}
// This code is contributed by subhamgoyal2014.
Python3
# Python code to implement the approach # Function to maximize the cost import sys def pickup(grid): M = len(grid) if (M == 0): return 0 N = len(grid[0]) if (N == 0): return 0 dp = [[[(-sys.maxsize-1) for i in range(N)] for j in range(N)] for k in range(M)] dp[0][0][N - 1] = grid[0][0] + grid[0][N - 1] for i in range(1,M): for a in range(N): for b in range(N): for l in range(a - 1,a + 2): for r in range(b - 1,b + 2): if (l < 0 or l >= N or r < 0 or r >= N): continue dp[i][a][b] = max(dp[i][a][b],(grid[i][a]+ grid[i][b] if (a != b) else grid[i][a]) + dp[i - 1][l][r]) ans = 0 for a in range(N): for b in range(N): ans = max(ans, dp[M - 1][a][b]) return ans # Driver code grid = [[ 3, 1, 1 ], [ 2, 5, 1 ], [ 1, 5, 5 ], [ 2, 1, 1 ]] print(pickup(grid)) # This code is contributed by shinjanpatra
C#
// C# code to implement the approach
using System;
class GFG
{
// Function to maximize the cost
static int pickup(int[,] grid)
{
int M = grid.GetLength(0);
if (M == 0)
return 0;
int N = grid.GetLength(1);
if (N == 0)
return 0;
int [,,]dp = new int[M,N,N];
dp[0,0,N - 1] = grid[0,0]
+ grid[0,N - 1];
for (int i = 1; i < M; i++)
for (int a = 0; a < N; a++)
for (int b = 0; b < N; b++)
for (int l = a - 1; l
<= a + 1;
l++)
for (int r = b - 1;
r <= b + 1; r++) {
if (l < 0 || l >= N
|| r < 0
|| r >= N)
continue;
dp[i,a,b] = Math.Max(
dp[i,a,b],
((a != b)
? grid[i,a]
+ grid[i,b]
: grid[i,a])
+ dp[i - 1,l,r]);
}
int ans = 0;
for (int a = 0; a < N; a++)
for (int b = 0; b < N; b++)
ans = Math.Max(ans, dp[M - 1,a,b]);
return ans;
}
// Driver code
public static void Main()
{
int[,] grid = {
{ 3, 1, 1 }, { 2, 5, 1 },
{ 1, 5, 5 }, { 2, 1, 1 }
};
Console.WriteLine( pickup(grid));
}}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript code for the above approach
// Function to maximize the cost
function pickup(grid) {
let M = grid.length;
if (M == 0)
return 0;
let N = grid[0].length;
if (N == 0)
return 0;
let dp = new Array(M);
for (let i = 0; i < dp.length; i++) {
dp[i] = new Array(N);
for (let j = 0; j < dp[i].length; j++) {
dp[i][j] = new Array(N).fill(Number.MIN_VALUE)
}
}
dp[0][0][N - 1] = grid[0][0]
+ grid[0][N - 1];
for (let i = 1; i < M; i++)
for (let a = 0; a < N; a++)
for (let b = 0; b < N; b++)
for (let l = a - 1; l
<= a + 1;
l++)
for (let r = b - 1;
r <= b + 1; r++) {
if (l < 0 || l >= N
|| r < 0
|| r >= N)
continue;
dp[i][a][b] = Math.max(
dp[i][a][b],
((a != b)
? grid[i][a]
+ grid[i][b]
: grid[i][a])
+ dp[i - 1][l][r]);
}
let ans = 0;
for (let a = 0; a < N; a++)
for (let b = 0; b < N; b++)
ans = Math.max(ans, dp[M - 1][a][b]);
return ans;
}
// Driver code
let grid = [
[3, 1, 1], [2, 5, 1],
[1, 5, 5], [2, 1, 1]
];
document.write(pickup(grid));
// This code is contributed by Potta Lokesh
</script>
Producción
24
Complejidad de Tiempo: O(M * N 2 )
Espacio Auxiliar: O(M * N 2 )
Implementación 2: con compresión de estado
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to maximize the cost
int pickup(vector<vector<int> >& grid)
{
int M = grid.size();
if (M == 0)
return 0;
int N = grid[0].size();
if (N == 0)
return 0;
vector<vector<vector<int> > > dp(
2, vector<vector<int> >(
N, vector<int>(N, INT_MIN)));
dp[0][0][N - 1] = grid[0][0]
+ grid[0][N - 1];
// Looping over all rows
for (int i = 1; i < M; i++)
// looping over every cell
// in the row for point1
for (int a = 0; a < N; a++)
// looping over every cell
// in the row for point2
for (int b = 0; b < N; b++)
// Capturing possible
// movements of point 1
for (int l = a - 1;
l <= a + 1; l++)
// Capturing possible
// movements of point2
for (int r = b - 1;
r <= b + 1; r++) {
if (l < 0 || l >= N
|| r < 0 || r >= N)
continue;
// Apply DP transition
dp[i % 2][a][b] = max(
dp[i % 2][a][b],
((a != b)
? grid[i][a]
+ grid[i][b]
: grid[i][a])
+ dp[(i - 1) % 2][l][r]);
}
// Loop over dp to get the final answer
int ans = 0;
for (int a = 0; a < N; a++)
for (int b = 0; b < N; b++)
ans = max(ans,
dp[(M - 1) % 2][a][b]);
return ans;
}
// Driver code
int main()
{
vector<vector<int> > grid{
{ 3, 1, 1 }, { 2, 5, 1 },
{ 1, 5, 5 }, { 2, 1, 1 }
};
cout << pickup(grid);
return 0;
}
Java
// Online Java Compiler
// Use this editor to write, compile and run your Java code online
class GFG {
public static int pickup(int[][] grid){
int M = grid.length;
if (M == 0)
return 0;
int N = grid[0].length;
if (N == 0)
return 0;
int dp[][][] = new int[2][N][N];
for(int i=0;i<2;i++){
for(int j=0;j<N;j++){
for(int k=0;k<N;k++){
dp[i][j][k] = Integer.MIN_VALUE;
}
}
}
dp[0][0][N - 1] = grid[0][0]
+ grid[0][N - 1];
// Looping over all rows
for (int i = 1; i < M; i++)
// looping over every cell
// in the row for point1
for (int a = 0; a < N; a++)
// looping over every cell
// in the row for point2
for (int b = 0; b < N; b++)
// Capturing possible
// movements of point 1
for (int l = a - 1;
l <= a + 1; l++)
// Capturing possible
// movements of point2
for (int r = b - 1;
r <= b + 1; r++) {
if (l < 0 || l >= N
|| r < 0 || r >= N)
continue;
// Apply DP transition
dp[i % 2][a][b] = Math.max(
dp[i % 2][a][b],
((a != b)
? grid[i][a]
+ grid[i][b]
: grid[i][a])
+ dp[(i - 1) % 2][l][r]);
}
// Loop over dp to get the final answer
int ans = 0;
for (int a = 0; a < N; a++)
for (int b = 0; b < N; b++)
ans = Math.max(ans,
dp[(M - 1) % 2][a][b]);
return ans;
}
public static void main(String[] args) {
int [][]grid = new int[][]{{ 3, 1, 1 }, { 2, 5, 1 },
{ 1, 5, 5 }, { 2, 1, 1 }};
System.out.println(pickup(grid));
}
}
// This code is contributed by akshitsexanaa09.
Python3
# Python code to implement the approach # Function to Math.maximize the cost import sys def pickup(grid): M = len(grid) if (M == 0): return 0 N = len(grid[0]) if (N == 0): return 0 dp = [[[-sys.maxsize -1 for i in range(N)]for j in range(N)]for k in range(2)] dp[0][0][N - 1] = grid[0][0] + grid[0][N - 1] # Looping over all rows for i in range(1,M): # looping over every cell # in the row for point1 for a in range(N): # looping over every cell # in the row for point2 for b in range(N): # Capturing possible # movements of point1 for l in range(a - 1,a + 2): # Capturing possible # movements of point2 for r in range(b - 1,b + 2): if (l < 0 or l >= N or r < 0 or r >= N): continue # Apply DP transition dp[i % 2][a][b] = max(dp[i % 2][a][b],(grid[i][a]+ grid[i][b] if (a != b) else grid[i][a]) + dp[(i - 1) % 2][l][r]) # Loop over dp to get the final answer ans = 0 for a in range(N): for b in range(N): ans = max(ans,dp[(M - 1) % 2][a][b]) return ans # Driver code grid = [ [ 3, 1, 1 ], [ 2, 5, 1 ], [ 1, 5, 5 ], [ 2, 1, 1 ] ] print(pickup(grid)) # This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript code to implement the approach
// Function to Math.maximize the cost
function pickup(grid)
{
let M = grid.length;
if (M == 0)
return 0;
let N = grid[0].length;
if (N == 0)
return 0;
let dp = new Array(2);
for(let i=0;i<2;i++){
dp[i] = new Array(N);
for(let j=0;j<N;j++){
dp[i][j] = new Array(N).fill(Number.MIN_VALUE);
}
}
dp[0][0][N - 1] = grid[0][0]
+ grid[0][N - 1];
// Looping over all rows
for (let i = 1; i < M; i++)
// looping over every cell
// in the row for point1
for (let a = 0; a < N; a++)
// looping over every cell
// in the row for point2
for (let b = 0; b < N; b++)
// Capturing possible
// movements of point 1
for (let l = a - 1;
l <= a + 1; l++)
// Capturing possible
// movements of point2
for (let r = b - 1;
r <= b + 1; r++) {
if (l < 0 || l >= N
|| r < 0 || r >= N)
continue;
// Apply DP transition
dp[i % 2][a][b] = Math.max(
dp[i % 2][a][b],
((a != b)
? grid[i][a]
+ grid[i][b]
: grid[i][a])
+ dp[(i - 1) % 2][l][r]);
}
// Loop over dp to get the final answer
let ans = 0;
for (let a = 0; a < N; a++)
for (let b = 0; b < N; b++)
ans = Math.max(ans,
dp[(M - 1) % 2][a][b]);
return ans
}
// Driver code
let grid = [ [ 3, 1, 1 ], [ 2, 5, 1 ],
[ 1, 5, 5 ], [ 2, 1, 1 ] ]
document.write(pickup(grid))
// This code is contributed by shinjanpatra
</script>
Producción
24
Complejidad de Tiempo: O(M * N 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por jayash1819 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA