Dada una array mat [][] de tamaño N * M y un número entero K , la tarea es encontrar una ruta desde la celda superior izquierda (0, 0 ) hasta la celda inferior derecha ( N–1, M–1 ) de la array dada tal que:
- Se permite un movimiento hacia la derecha y hacia abajo. es decir, de (i, j) a (i, j-1) y (i+1, j).
- La suma de los elementos en la ruta es máxima y no se pueden elegir más de K celdas de una fila.
Ejemplos:
Entrada : N = 3, M = 3, K = 2, mat = [[2, 10, 8], [8, 8, 8], [0, 1, 0]]
Salida : 28
Explicación : La forma óptima de elegir celdas será (0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (2, 2).Entrada : N = 3, M = 3, K = 1, mat = [[0, 0, 4], [0, 5, 0], [3, 0, 2]]
Salida : 7
Explicación : La forma óptima de elegir celdas será (0, 0) -> (1, 0) -> (1, 1) -> (1, 2) -> (2, 2).
Enfoque ingenuo: el enfoque más fácil es encontrar todas las rutas posibles desde la parte superior izquierda hasta la parte inferior derecha y no tener más de K celdas de una sola fila. Calcule la suma máxima de caminos entre todos ellos.
Complejidad de Tiempo: O( M+N-2 C N-1 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque eficiente para resolver el problema es usar programación dinámica basada en la siguiente idea:
Para cualquier fila, considere que se eligen del 1 al K número de elementos de esa fila.
Para cualquier celda (i, j) considérela como parte de la ruta eligiendo l número de celdas de esa fila.
Cree una array de dp 3D donde dp[i][j][l] almacene el valor calculado cuando la celda (i, j) sea parte de una ruta que tenga l celdas de esa fila.
- dp[i][j][l] depende de dp[i][j][l-1] y dp[i][j-1][l] .
- dp[i][j][0] depende de dp[i-1][j][l] para todos los valores de l de 1 a K (porque cuando se cambia la fila no se toma ningún elemento de la nueva fila hasta ahora) .
Siga los pasos a continuación para resolver este problema :
- Declare una array 3D (digamos dp ) con tamaño N * M * (K + 1) .
- Iterar sobre la array dada:
- Iterar sobre todos los valores posibles de l en orden inverso (de K-1 a 0 ):
- Compruebe si el estado actual de dp tiene un valor positivo.
- Luego actualice la array dp para (l + 1)-ésimo estado ya que incluimos el valor actual de la cuadrícula.
- Nuevamente iterar sobre todos los valores posibles de l :
- Compruebe si el estado actual de dp tiene un valor positivo.
- Luego, actualice la celda hacia abajo de la celda actual, si existe.
- Y también actualice la celda hacia la derecha de la celda actual, si existe.
- Iterar sobre todos los valores posibles de l en orden inverso (de K-1 a 0 ):
- Declare una variable entera ans e inicialícela con 0.
- Iterar sobre todos los valores posibles de l .
- Actualice ans como max de sí mismo y el dp[N-1][M-1][l].
- Finalmente, devuelva el ans .
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;
// Function to find the maximum path sum
int maximumProfits(int n, int m, int k,
vector<vector<int> >& grid)
{
// Declare a -d array named “dp”
// with size ‘N’ * ‘M’ * (‘K’ + 1).
int dp[n][m][k + 1];
// Initialize the "dp" array with INT_MIN.
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int l = 0; l < k + 1; l++) {
dp[i][j][l] = INT_MIN;
}
}
}
// Base case.
dp[0][0][0] = 0;
// Iterate over the grid.
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Iterate over the possible
// values of ‘l’ in reverse order.
for (int l = k - 1; l >= 0; l--) {
// If the current state
// of “dp” has positive value
if (dp[i][j][l] >= 0) {
// Update “dp” array for
//(‘l’ + 1)-th state since
// we include
// the current value
// of the grid.
dp[i][j][l + 1]
= max(dp[i][j][l + 1],
dp[i][j][l]
+ grid[i][j]);
}
}
// Again iterate over
// all possible values of ‘l’.
for (int l = 0; l < k + 1; l++) {
// If the current state
// of “dp” has positive value
if (dp[i][j][l] >= 0) {
// Update the downward cell
// of the current cell
// if it exists.
if (i + 1 < n) {
dp[i + 1][j][0] = max(
dp[i + 1][j][0],
dp[i][j][l]);
}
// Update the right cell
// of the current cell
// if it exists.
if (j + 1 < m) {
dp[i][j + 1][l] = max(
dp[i][j + 1][l],
dp[i][j][l]);
}
}
}
}
}
// Declare an integer variable “ans” and
// initialize it with 0.
int ans = 0;
// Iterate over all possible values of l
for (int l = 0; l < k + 1; l++) {
// Update ans as max of itself and
// the dp value for (n -1, m - 1)th
// cell for the current value of l
ans = max(ans, dp[n - 1][m - 1][l]);
}
// Return the “ans”.
return ans;
}
// Driver code
int main()
{
int N = 3, M = 3, K = 2;
vector<vector<int> > mat = { { 2, 10, 8 },
{ 8, 8, 8 },
{ 0, 1, 0 } };
cout << maximumProfits(N, M, K, mat);
return 0;
}
Java
// JAVA code to implement the approach
import java.util.*;
class GFG {
// Function to find the maximum path sum
public static int
maximumProfits(int n, int m, int k,
ArrayList<ArrayList<Integer> > grid)
{
// Declare a -d array named “dp”
// with size ‘N’ * ‘M’ * (‘K’ + 1).
int dp[][][] = new int[n][m][k + 1];
// Initialize the "dp" array with INT_MIN.
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int l = 0; l < k + 1; l++) {
dp[i][j][l] = Integer.MIN_VALUE;
}
}
}
// Base case.
dp[0][0][0] = 0;
// Iterate over the grid.
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Iterate over the possible
// values of ‘l’ in reverse order.
for (int l = k - 1; l >= 0; l--) {
// If the current state
// of “dp” has positive value
if (dp[i][j][l] >= 0) {
// Update “dp” array for
//(‘l’ + 1)-th state since
// we include
// the current value
// of the grid.
dp[i][j][l + 1] = Math.max(
dp[i][j][l + 1],
dp[i][j][l]
+ grid.get(i).get(j));
}
}
// Again iterate over
// all possible values of ‘l’.
for (int l = 0; l < k + 1; l++) {
// If the current state
// of “dp” has positive value
if (dp[i][j][l] >= 0) {
// Update the downward cell
// of the current cell
// if it exists.
if (i + 1 < n) {
dp[i + 1][j][0]
= Math.max(dp[i + 1][j][0],
dp[i][j][l]);
}
// Update the right cell
// of the current cell
// if it exists.
if (j + 1 < m) {
dp[i][j + 1][l]
= Math.max(dp[i][j + 1][l],
dp[i][j][l]);
}
}
}
}
}
// Declare an integer variable “ans” and
// initialize it with 0.
int ans = 0;
// Iterate over all possible values of l
for (int l = 0; l < k + 1; l++) {
// Update ans as max of itself and
// the dp value for (n -1, m - 1)th
// cell for the current value of l
ans = Math.max(ans, dp[n - 1][m - 1][l]);
}
// Return the “ans”.
return ans;
}
// Driver code
public static void main(String[] args)
{
int N = 3, M = 3, K = 2;
ArrayList<ArrayList<Integer> > mat
= new ArrayList<ArrayList<Integer> >();
ArrayList<Integer> temp1 = new ArrayList<Integer>(
Arrays.asList(2, 10, 8));
ArrayList<Integer> temp2 = new ArrayList<Integer>(
Arrays.asList(8, 8, 8));
ArrayList<Integer> temp3 = new ArrayList<Integer>(
Arrays.asList(0, 1, 0));
mat.add(temp1);
mat.add(temp2);
mat.add(temp3);
System.out.print(maximumProfits(N, M, K, mat));
}
}
// This code is contributed by Taranpreet
Python3
# Python code to implement the approach import sys INT_MIN = -sys.maxsize - 1 # Function to find the maximum path sum def maximumProfits(n, m, k,grid): global INT_MIN # Declare a -d array named “dp” # with size ‘N’ * ‘M’ * (‘K’ + 1). # Initialize the "dp" array with INT_MIN. dp = [[[INT_MIN for i in range(k + 1)] for j in range(m)] for l in range(n)] # Base case. dp[0][0][0] = 0 # Iterate over the grid. for i in range(n): for j in range(m): # Iterate over the possible # values of ‘l’ in reverse order. for l in range(k - 1,-1,-1): # If the current state # of “dp” has positive value if (dp[i][j][l] >= 0): # Update “dp” array for #(‘l’ + 1)-th state since # we include # the current value # of the grid. dp[i][j][l + 1] = max(dp[i][j][l + 1],dp[i][j][l] + grid[i][j]) # Again iterate over # all possible values of ‘l’. for l in range(k + 1): # If the current state # of “dp” has positive value if (dp[i][j][l] >= 0): # Update the downward cell # of the current cell # if it exists. if (i + 1 < n): dp[i + 1][j][0] = max(dp[i + 1][j][0],dp[i][j][l]) # Update the right cell # of the current cell # if it exists. if (j + 1 < m): dp[i][j + 1][l] = max(dp[i][j + 1][l],dp[i][j][l]) # Declare an integer variable “ans” and # initialize it with 0. ans = 0 # Iterate over all possible values of l for l in range(k + 1): # Update ans as max of itself and # the dp value for (n -1, m - 1)th # cell for the current value of l ans = max(ans, dp[n - 1][m - 1][l]) # Return the “ans”. return ans # Driver code N, M, K = 3, 3, 2 mat = [ [ 2, 10, 8 ],[ 8, 8, 8 ],[ 0, 1, 0 ] ] print(maximumProfits(N, M, K, mat)) # This code is contributed by shinjanpatra.
C#
// C# code to implement the approach
using System;
using System.Collections.Generic;
public class GFG{
// Function to find the maximum path sum
static int
maximumProfits(int n, int m, int k,
List<List<int> > grid)
{
// Declare a -d array named “dp”
// with size ‘N’ * ‘M’ * (‘K’ + 1).
int[, ,] dp = new int[n,m,k + 1];
// Initialize the "dp" array with INT_MIN.
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int l = 0; l < k + 1; l++) {
dp[i, j, l] = Int32.MinValue;
}
}
}
// Base case.
dp[0,0,0] = 0;
// Iterate over the grid.
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Iterate over the possible
// values of ‘l’ in reverse order.
for (int l = k - 1; l >= 0; l--) {
// If the current state
// of “dp” has positive value
if (dp[i,j,l] >= 0) {
// Update “dp” array for
//(‘l’ + 1)-th state since
// we include
// the current value
// of the grid.
dp[i, j,l+1] = Math.Max(
dp[i, j,l+1],
dp[i, j,l]
+ grid[i][j]);
}
}
// Again iterate over
// all possible values of ‘l’.
for (int l = 0; l < k + 1; l++) {
// If the current state
// of “dp” has positive value
if (dp[i,j,l] >= 0) {
// Update the downward cell
// of the current cell
// if it exists.
if (i + 1 < n) {
dp[i + 1,j,0]
= Math.Max(dp[i + 1,j,0],
dp[i,j,l]);
}
// Update the right cell
// of the current cell
// if it exists.
if (j + 1 < m) {
dp[i,j + 1,l]
= Math.Max(dp[i,j + 1,l],
dp[i,j, l]);
}
}
}
}
}
// Declare an integer variable “ans” and
// initialize it with 0.
int ans = 0;
// Iterate over all possible values of l
for (int l = 0; l < k + 1; l++) {
// Update ans as max of itself and
// the dp value for (n -1, m - 1)th
// cell for the current value of l
ans = Math.Max(ans, dp[n - 1,m - 1,l]);
}
// Return the “ans”.
return ans;
}
// Driver code
static public void Main (){
int N = 3, M = 3, K = 2;
List<List<int>> mat = new List<List<int>>();
mat.Add(new List<int> {2, 10, 8 });
mat.Add(new List<int> { 8, 8, 8 });
mat.Add(new List<int> { 0, 1, 0 });
Console.Write(maximumProfits(N, M, K, mat));
}
}
// This code is contributed by hrithikgarg03188.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the maximum path sum
function maximumProfits(n, m, k,
grid) {
// Declare a -d array named “dp”
// with size ‘N’ * ‘M’ * (‘K’ + 1).
let dp = new Array(n);
for (let i = 0; i < dp.length; i++) {
dp[i] = new Array(m)
for (let j = 0; j < dp[i].length; j++) {
dp[i][j] = new Array(k + 1)
}
}
// Initialize the "dp" array with INT_MIN.
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
for (let l = 0; l < k + 1; l++) {
dp[i][j][l] = Number.MIN_VALUE;
}
}
}
// Base case.
dp[0][0][0] = 0;
// Iterate over the grid.
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
// Iterate over the possible
// values of ‘l’ in reverse order.
for (let l = k - 1; l >= 0; l--) {
// If the current state
// of “dp” has positive value
if (dp[i][j][l] >= 0) {
// Update “dp” array for
//(‘l’ + 1)-th state since
// we include
// the current value
// of the grid.
dp[i][j][l + 1]
= Math.max(dp[i][j][l + 1],
dp[i][j][l]
+ grid[i][j]);
}
}
// Again iterate over
// all possible values of ‘l’.
for (let l = 0; l < k + 1; l++) {
// If the current state
// of “dp” has positive value
if (dp[i][j][l] >= 0) {
// Update the downward cell
// of the current cell
// if it exists.
if (i + 1 < n) {
dp[i + 1][j][0] = Math.max(
dp[i + 1][j][0],
dp[i][j][l]);
}
// Update the right cell
// of the current cell
// if it exists.
if (j + 1 < m) {
dp[i][j + 1][l] = Math.max(
dp[i][j + 1][l],
dp[i][j][l]);
}
}
}
}
}
// Declare an integer variable “ans” and
// initialize it with 0.
let ans = 0;
// Iterate over all possible values of l
for (let l = 0; l < k + 1; l++) {
// Update ans as max of itself and
// the dp value for (n -1, m - 1)th
// cell for the current value of l
ans = Math.max(ans, dp[n - 1][m - 1][l]);
}
// Return the “ans”.
return ans;
}
// Driver code
let N = 3, M = 3, K = 2;
let mat = [[2, 10, 8],
[8, 8, 8],
[0, 1, 0]];
document.write(maximumProfits(N, M, K, mat));
// This code is contributed by Potta Lokesh
</script>
Producción
28
Tiempo Complejidad: O (N * M * K)
Espacio Auxiliar: O (N * M * K)