Dada una array N x N donde el valor en la celda (i, j) es el costo de pasar de una celda (i, j) a la celda (i – 1, j – 1), (i – 1, j) o (i , j – 1). Su tarea es encontrar la ruta de costo máximo desde la celda (N – 1, N – 1) hasta la celda (0, 0) en la array N x N (indexación basada en 0). Sin embargo, tiene algunas restricciones en el movimiento de una celda a otra celda. Si está en la celda (i, j) y (i + j) es una potencia de 2, solo puede moverse a la celda (i – 1, j – 1). Si (i + j) no es una potencia de 2, puede pasar a (i – 1, j) o (i, j – 1)
Ejemplos:
Input :[1 2 3 1
4 5 6 1
7 8 9 1
1 1 1 1]
Output: 16
The maximum cost path is:
(3, 3) -> (3, 2) -> (2, 2) -> (1, 1) -> (0, 0).
Cost pathwise is:
1 + 1 + 9 + 5 = 16.
Input: [1 2
3 4]
Output: 4
Subestructura Óptima:
El problema es una variación del problema Min-Cost . El camino para llegar a (0, 0) desde (n-1, n-1) debe ser a través de las tres celdas (i, j-1) o (i-1, j) o (i-1, j-1) . Se llamará a una función recursiva de arriba hacia abajo, para cada valor de m y n, verifique si (m+n) es una potencia de 2 o no. Si es una potencia de 2, muévase a la celda (m-1, n-1) y agregue el valor en a[m][n]. Por lo tanto el costo será:
costo = a[m][n] + maxCost(a, m – 1, n – 1)
Si no es una potencia de 2, podemos movernos a dos de las celdas (m-1, n) y (m, n-1). Entonces el costo será:
costo = a[m][n] + max(maxCost(a, m – 1, n), maxCost(a, m, n – 1))
A continuación se muestra la implementación recursiva del enfoque anterior:
C++
// C++ program for
// SP - Wolfish
#include <bits/stdc++.h>
using namespace std;
const int size = 1000;
// Function to find the maxCost of path from
// (n-1, n-1) to (0, 0) | recursive approach
int maxCost(int a[][size], int m, int n)
{
// base condition
if (n < 0 || m < 0)
return -1e9;
// reaches the point
else if (m == 0 && n == 0)
return 0;
else {
// i + j
int num = m + n;
// check if it is a power of 2,
// then only move diagonally
if ((num & (num - 1)) == 0)
return a[m][n] + maxCost(a, m - 1, n - 1);
// if not a power of 2
// then move side-wise
else
return a[m][n] + max(maxCost(a, m - 1, n),
maxCost(a, m, n - 1));
}
}
// Function to return the maximum cost
int answer(int a[][size], int n)
{
// calling dp function to get the answer
return maxCost(a, n - 1, n - 1);
}
// Driver Code
int main()
{
int a[][size] = { { 1, 2, 3, 1 },
{ 4, 5, 6, 1 },
{ 7, 8, 9, 1 },
{ 1, 1, 1, 1 } };
int n = 4;
// Function calling to get the answer
cout << answer(a, n);
return 0;
}
Java
// Java program for SP - Wolfish
class GFG {
static int size = 1000;
// Function to find the maxCost of path from
// (n-1, n-1) to (0, 0) | recursive approach
public static int maxCost(int[][] a, int m, int n)
{
// base condition
if (n < 0 || m < 0) {
return -1;
}
// reaches the point
else if (m == 0 && n == 0) {
return 0;
}
else {
// i + j
int num = m + n;
// check if it is a power of 2,
// then only move diagonally
if ((num & (num - 1)) == 0) {
return a[m][n] + maxCost(a, m - 1, n - 1);
}
// if not a power of 2
// then move side-wise
else {
return a[m][n] + Math.max(maxCost(a, m - 1, n), maxCost(a, m, n - 1));
}
}
}
// Function to return the maximum cost
public static int answer(int[][] a, int n)
{
// calling dp function to get the answer
return maxCost(a, n - 1, n - 1);
}
// Driver Code
public static void main(String[] args)
{
int[][] a = new int[][] { { 1, 2, 3, 1 },
{ 4, 5, 6, 1 },
{ 7, 8, 9, 1 },
{ 1, 1, 1, 1 } };
int n = 4;
System.out.println(answer(a, n));
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python program for # SP - Wolfish size = 1000 # Function to find the maxCost of path from # (n-1, n-1) to (0, 0) | recursive approach def maxCost(a: list, m: int, n: int) -> int: # base condition if n < 0 or m < 0: return int(-1e9) # reaches the point elif m == 0 and n == 0: return 0 else: # i + j num = m + n # check if it is a power of 2, # then only move diagonally if (num & (num - 1)) == 0: return a[m][n] + maxCost(a, m - 1, n - 1) # if not a power of 2 # then move side-wise else: return a[m][n] + max(maxCost(a, m - 1, n), maxCost(a, m, n - 1)) # Function to return the maximum cost def answer(a: list, n: int) -> int: # calling dp function to get the answer return maxCost(a, n - 1, n - 1) # Driver Code if __name__ == "__main__": a = [[1, 2, 3, 1], [4, 5, 6, 1], [7, 8, 9, 1], [1, 1, 1, 1]] n = 4 # Function calling to get the answer print(answer(a, n)) # This code is contributed by # sanjeev2552
C#
// C# program for
// SP - Wolfish
using System;
class GFG {
static int size = 1000;
// Function to find the maxCost of path from
// (n-1, n-1) to (0, 0) | recursive approach
public static int maxCost(int[, ] a, int m, int n)
{
// base condition
if (n < 0 || m < 0)
return -1;
// reaches the point
else if (m == 0 && n == 0)
return 0;
else {
// i + j
int num = m + n;
// check if it is a power of 2,
// then only move diagonally
if ((num & (num - 1)) == 0)
return a[m, n] + maxCost(a, m - 1, n - 1);
// if not a power of 2
// then move side-wise
else
return a[m, n] + Math.Max(maxCost(a, m - 1, n), maxCost(a, m, n - 1));
}
}
// Function to return the maximum cost
public static int answer(int[, ] a, int n)
{
// calling dp function to get the answer
return maxCost(a, n - 1, n - 1);
}
// Driver Code
static void Main()
{
int[, ] a = new int[, ] { { 1, 2, 3, 1 },
{ 4, 5, 6, 1 },
{ 7, 8, 9, 1 },
{ 1, 1, 1, 1 } };
int n = 4;
// Function calling to get the answer
Console.Write(answer(a, n));
}
// This code is contributed by DrRoot_
}
Javascript
<script>
// Javascript program for SP - Wolfish
let size = 1000;
// Function to find the maxCost of path from
// (n-1, n-1) to (0, 0) | recursive approach
function maxCost(a,m,n)
{
// base condition
if (n < 0 || m < 0) {
return -1;
}
// reaches the point
else if (m == 0 && n == 0) {
return 0;
}
else {
// i + j
let num = m + n;
// check if it is a power of 2,
// then only move diagonally
if ((num & (num - 1)) == 0) {
return a[m][n] + maxCost(a, m - 1, n - 1);
}
// if not a power of 2
// then move side-wise
else {
return a[m][n] + Math.max(maxCost(a, m - 1, n), maxCost(a, m, n - 1));
}
}
}
// Function to return the maximum cost
function answer(a,n)
{
// calling dp function to get the answer
return maxCost(a, n - 1, n - 1);
}
// Driver Code
let a=[[ 1, 2, 3, 1 ],[ 4, 5, 6, 1 ],
[ 7, 8, 9, 1 ],
[ 1, 1, 1, 1 ]];
let n = 4;
document.write(answer(a, n));
// This code is contributed by rag2127
</script>
Producción:
16
Complejidad del tiempo: O(2 N )
Enfoque usando Memoización
En la recursividad anterior, muchos subproblemas se llaman repetidamente. Para reducir el número de llamadas repetitivas, se ha utilizado la memorización. El punto común de observación es que solo el valor de dos parámetros cambia en cada llamada de función. Entonces, si memorizamos el valor devuelto en una array dp[][], la cantidad de llamadas se reducirá a N^2. Por lo tanto, almacene el valor calculado de cada maxCost(m, n) en dp[m][n]. Si maxCost(m, n) se llama más de una vez, las llamadas adicionales de la función se reducirán al devolver el valor almacenado en dp[m][n].
A continuación se muestra la implementación eficiente del enfoque anterior:
C++
// C++ program for SP - Wolfish
#include <bits/stdc++.h>
using namespace std;
const int size = 1000;
// Function to find the maxCost of path from
// (n-1, n-1) to (0, 0)
int maxCost(int a[][size], int m, int n, int dp[][size])
{
// base condition
if (n < 0 || m < 0)
return -1e9;
// reaches the point
else if (m == 0 && n == 0)
return 0;
// if the state has been visited previously
else if (dp[m][n] != -1)
return dp[m][n];
else {
// i + j
int num = m + n;
// check if it is a power of 2,
// then only move diagonally
if ((num & (num - 1)) == 0)
return dp[m][n] = a[m][n] + maxCost(a, m - 1, n - 1, dp);
// if not a power of 2
// then move side-wise
else
return dp[m][n] = (a[m][n] + max(maxCost(a, m - 1, n, dp),
maxCost(a, m, n - 1, dp)));
}
}
// Function to return the maximum cost
int answer(int a[][size], int n)
{
int dp[size][size];
memset(dp, -1, sizeof dp);
// calling dp function to get the answer
return maxCost(a, n - 1, n - 1, dp);
}
// Driver Code
int main()
{
int a[][size] = { { 1, 2, 3, 1 },
{ 4, 5, 6, 1 },
{ 7, 8, 9, 1 },
{ 1, 1, 1, 1 } };
int n = 4;
// Function calling to get the answer
cout << answer(a, n);
return 0;
}
Java
// Java program for SP - Wolfish
class GFG {
static int size = 1000;
// Function to find the maxCost of path from
// (n-1, n-1) to (0, 0)
static int maxCost(int a[][], int m, int n, int dp[][])
{
// base condition
if (n < 0 || m < 0)
return (int)-1e9;
// reaches the point
else if (m == 0 && n == 0)
return 0;
// if the state has been visited previously
else if (dp[m][n] != -1)
return dp[m][n];
else {
// i + j
int num = m + n;
// check if it is a power of 2,
// then only move diagonally
if ((num & (num - 1)) == 0)
return dp[m][n] = a[m][n] + maxCost(a, m - 1, n - 1, dp);
// if not a power of 2
// then move side-wise
else
return dp[m][n] = (a[m][n] + Math.max(maxCost(a, m - 1, n, dp),
maxCost(a, m, n - 1, dp)));
}
}
// Function to return the maximum cost
static int answer(int a[][], int n)
{
int dp[][] = new int[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
dp[i][j] = -1;
}
}
// calling dp function to get the answer
return maxCost(a, n - 1, n - 1, dp);
}
// Driver Code
public static void main(String[] args)
{
int a[][] = { { 1, 2, 3, 1 },
{ 4, 5, 6, 1 },
{ 7, 8, 9, 1 },
{ 1, 1, 1, 1 } };
int n = 4;
// Function calling to get the answer
System.out.println(answer(a, n));
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python program for SP - Wolfish size = 1000; # Function to find the maxCost of path from # (n-1, n-1) to (0, 0) def maxCost(a, m, n, dp): # base condition if (n < 0 or m < 0): return int(-1e9); # reaches the point elif(m == 0 and n == 0): return 0; # if the state has been visited previously elif(dp[m][n] != -1): return dp[m][n]; else: # i + j num = m + n; # check if it is a power of 2, # then only move diagonally if ((num & (num - 1)) == 0): dp[m][n] = a[m][n] + maxCost(a, m - 1, n - 1, dp); return dp[m][n]; # if not a power of 2 # then move side-wise else: dp[m][n] = (a[m][n] + max(maxCost(a, m - 1, n, dp), maxCost(a, m, n - 1, dp))); return dp[m][n]; # Function to return the maximum cost def answer(a, n): dp = [[0 for i in range(size)] for j in range(size)] ; for i in range(size): for j in range(size): dp[i][j] = -1; # calling dp function to get the answer return maxCost(a, n - 1, n - 1, dp); # Driver Code if __name__ == '__main__': a = [[ 1, 2, 3, 1 ],[ 4, 5, 6, 1 ],[ 7, 8, 9, 1 ],[ 1, 1, 1, 1 ]]; n = 4; # Function calling to get the answer print(answer(a, n)); # This code contributed by Rajput-Ji
C#
// C# program for SP - Wolfish
using System;
class GFG
{
static int size = 1000;
// Function to find the maxCost of path from
// (n-1, n-1) to (0, 0)
static int maxCost(int [,]a, int m, int n, int [,]dp)
{
// base condition
if (n < 0 || m < 0)
return (int)-1e9;
// reaches the point
else if (m == 0 && n == 0)
return 0;
// if the state has been visited previously
else if (dp[m, n] != -1)
return dp[m,n];
else {
// i + j
int num = m + n;
// check if it is a power of 2,
// then only move diagonally
if ((num & (num - 1)) == 0)
return dp[m, n] = a[m, n] + maxCost(a, m - 1, n - 1, dp);
// if not a power of 2
// then move side-wise
else
return dp[m,n] = (a[m,n] + Math.Max(maxCost(a, m - 1, n, dp),
maxCost(a, m, n - 1, dp)));
}
}
// Function to return the maximum cost
static int answer(int [,]a, int n)
{
int [,]dp = new int[size,size];
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
dp[i, j] = -1;
}
}
// calling dp function to get the answer
return maxCost(a, n - 1, n - 1, dp);
}
// Driver Code
public static void Main(String[] args)
{
int [,]a = { { 1, 2, 3, 1 },
{ 4, 5, 6, 1 },
{ 7, 8, 9, 1 },
{ 1, 1, 1, 1 } };
int n = 4;
// Function calling to get the answer
Console.WriteLine(answer(a, n));
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript program for SP - Wolfish
let size = 1000;
// Function to find the maxCost of path from
// (n-1, n-1) to (0, 0)
function maxCost(a,m,n,dp)
{
// base condition
if (n < 0 || m < 0)
return -1e9;
// reaches the point
else if (m == 0 && n == 0)
return 0;
// if the state has been visited previously
else if (dp[m][n] != -1)
return dp[m][n];
else {
// i + j
let num = m + n;
// check if it is a power of 2,
// then only move diagonally
if ((num & (num - 1)) == 0)
return dp[m][n] = a[m][n] + maxCost(a, m - 1, n - 1, dp);
// if not a power of 2
// then move side-wise
else
return dp[m][n] = (a[m][n] + Math.max(maxCost(a, m - 1, n, dp),
maxCost(a, m, n - 1, dp)));
}
}
// Function to return the maximum cost
function answer(a,n)
{
let dp = new Array(size);
for (let i = 0; i < size; i++) {
dp[i]=new Array(size);
for (let j = 0; j < size; j++) {
dp[i][j] = -1;
}
}
// calling dp function to get the answer
return maxCost(a, n - 1, n - 1, dp);
}
// Driver Code
let a=[[ 1, 2, 3, 1 ],
[ 4, 5, 6, 1 ],
[ 7, 8, 9, 1 ],
[ 1, 1, 1, 1 ]];
let n = 4;
// Function calling to get the answer
document.write(answer(a, n));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
16
Complejidad de tiempo: O(N 2 )
Espacio auxiliar: O(N 2 )
Nota: Para implementar un enfoque ascendente, debemos verificar si ((m+1) + (n+1)) es una potencia de 2 o no en lugar de (m+n) ya que los movimientos están en orden de arriba hacia abajo.