Dada una array de N filas y M columnas. Desde m[i][j], podemos movernos a m[i+1][j], si m[i+1][j] > m[i][j], o podemos movernos a m[i] [j+1] si m[i][j+1] > m[i][j]. La tarea es imprimir la ruta más larga si comenzamos desde (0, 0).
Ejemplos:
Input : N = 4, M = 4
m[][] = { { 1, 2, 3, 4 },
{ 2, 2, 3, 4 },
{ 3, 2, 3, 4 },
{ 4, 5, 6, 7 } };
Output : 7
Longest path is 1 2 3 4 5 6 7.
Input : N = 2, M =2
m[][] = { { 1, 2 },
{ 3, 4 } };
Output :3
Longest path is either 1 2 4 or
1 3 4.
La idea es usar programación dinámica. Mantenga la array 2D, dp[][], donde dp[i][j] almacene el valor de la longitud de la secuencia creciente más larga para la subarray a partir de la i-ésima fila y la j-ésima columna.
Deje que los valores de subsecuencia crecientes más largos para m[i+1][j] y m[i][j+1] ya se conozcan como v1 y v2 respectivamente. Entonces, el valor de m[i][j] será max(v1, v2) + 1.
Podemos comenzar desde m[n-1][m-1] como el caso base con la longitud de la subsecuencia creciente más larga de 1 , moviéndose hacia arriba y hacia la izquierda actualizando el valor de las celdas. Entonces el valor LIP para la celda m[0][0] será la respuesta.
A continuación se muestra la implementación de este enfoque:
C++
// CPP program to find longest increasing
// path in a matrix.
#include <bits/stdc++.h>
#define MAX 10
using namespace std;
// Return the length of LIP in 2D matrix
int LIP(int dp[][MAX], int mat[][MAX], int n, int m, int x, int y)
{
// If value not calculated yet.
if (dp[x][y] < 0) {
int result = 0;
// If reach bottom right cell, return 1.
if (x == n - 1 && y == m - 1)
return dp[x][y] = 1;
// If reach the corner of the matrix.
if (x == n - 1 || y == m - 1)
result = 1;
// If value greater than below cell.
if(x != n-1) // x reaches last row
if (mat[x][y] < mat[x + 1][y])
result = 1 + LIP(dp, mat, n, m, x + 1, y);
// If value greater than left cell.
if(y != m-1) // y reaches last column
if (mat[x][y] < mat[x][y + 1])
result = max(result, 1 + LIP(dp, mat, n, m, x, y + 1));
dp[x][y] = result;
}
return dp[x][y];
}
// Wrapper function
int wrapper(int mat[][MAX], int n, int m)
{
int dp[MAX][MAX];
memset(dp, -1, sizeof dp);
return LIP(dp, mat, n, m, 0, 0);
}
// Driven Program
int main()
{
int mat[][MAX] = {
{ 1, 2, 3, 4 },
{ 2, 2, 3, 4 },
{ 3, 2, 3, 4 },
{ 4, 5, 6, 7 },
};
int n = 4, m = 4;
cout << wrapper(mat, n, m) << endl;
return 0;
}
Java
// Java program to find longest increasing
// path in a matrix.
import java.util.*;
class GFG {
// Return the length of LIP in 2D matrix
static int LIP(int dp[][], int mat[][], int n,
int m, int x, int y)
{
// If value not calculated yet.
if (dp[x][y] < 0) {
int result = 0;
// If reach bottom right cell, return 1.
if (x == n - 1 && y == m - 1)
return dp[x][y] = 1;
// If reach the corner of the matrix.
if (x == n - 1 || y == m - 1)
result = 1;
// If value greater than below cell.
if (x + 1 < n && mat[x][y] < mat[x + 1][y])
result = 1 + LIP(dp, mat, n, m, x + 1, y);
// If value greater than left cell.
if (y + 1 < m && mat[x][y] < mat[x][y + 1])
result = Math.max(result, 1 + LIP(dp, mat, n, m, x, y + 1));
dp[x][y] = result;
}
return dp[x][y];
}
// Wrapper function
static int wrapper(int mat[][], int n, int m)
{
int dp[][] = new int[10][10];
for (int i = 0; i < 10; i++)
Arrays.fill(dp[i], -1);
return LIP(dp, mat, n, m, 0, 0);
}
/* Driver program to test above function */
public static void main(String[] args)
{
int mat[][] = {
{ 1, 2, 3, 4 },
{ 2, 2, 3, 4 },
{ 3, 2, 3, 4 },
{ 4, 5, 6, 7 },
};
int n = 4, m = 4;
System.out.println(wrapper(mat, n, m));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 program to find longest # increasing path in a matrix. MAX = 20 # Return the length of # LIP in 2D matrix def LIP(dp, mat, n, m, x, y): # If value not calculated yet. if (dp[x][y] < 0): result = 0 # // If reach bottom right cell, return 1 if (x == n - 1 and y == m - 1): dp[x][y] = 1 return dp[x][y] # If reach the corner # of the matrix. if (x == n - 1 or y == m - 1): result = 1 # If value greater than below cell. if (x + 1 < n and mat[x][y] < mat[x + 1][y]): result = 1 + LIP(dp, mat, n, m, x + 1, y) # If value greater than left cell. if (y + 1 < m and mat[x][y] < mat[x][y + 1]): result = max(result, 1 + LIP(dp, mat, n, m, x, y + 1)) dp[x][y] = result return dp[x][y] # Wrapper function def wrapper(mat, n, m): dp = [[-1 for i in range(MAX)] for i in range(MAX)] return LIP(dp, mat, n, m, 0, 0) # Driver Code mat = [[1, 2, 3, 4 ], [2, 2, 3, 4 ], [3, 2, 3, 4 ], [4, 5, 6, 7 ]] n = 4 m = 4 print(wrapper(mat, n, m)) # This code is contributed # by Sahil Shelangia
C#
// C# program to find longest increasing
// path in a matrix.
using System;
public class GFG {
// Return the length of LIP in 2D matrix
static int LIP(int[, ] dp, int[, ] mat, int n,
int m, int x, int y)
{
// If value not calculated yet.
if (dp[x, y] < 0) {
int result = 0;
// If reach bottom right cell, return 1.
if (x == n - 1 && y == m - 1)
return dp[x, y] = 1;
// If reach the corner of the matrix.
if (x == n - 1 || y == m - 1)
result = 1;
// If value greater than below cell.
if (x + 1 < n && mat[x, y] < mat[x + 1, y])
result = 1 + LIP(dp, mat, n, m, x + 1, y);
// If value greater than left cell.
if (y + 1 < m && mat[x, y] < mat[x, y + 1])
result = Math.Max(result, 1 + LIP(dp, mat, n, m, x, y + 1));
dp[x, y] = result;
}
return dp[x, y];
}
// Wrapper function
static int wrapper(int[, ] mat, int n, int m)
{
int[, ] dp = new int[10, 10];
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
dp[i, j] = -1;
}
}
return LIP(dp, mat, n, m, 0, 0);
}
/* Driver code */
public static void Main()
{
int[, ] mat = {
{ 1, 2, 3, 4 },
{ 2, 2, 3, 4 },
{ 3, 2, 3, 4 },
{ 4, 5, 6, 7 },
};
int n = 4, m = 4;
Console.WriteLine(wrapper(mat, n, m));
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript program to find longest increasing path in a matrix.
// Return the length of LIP in 2D matrix
function LIP(dp, mat, n, m, x, y)
{
// If value not calculated yet.
if (dp[x][y] < 0) {
let result = 0;
// If reach bottom right cell, return 1.
if (x == n - 1 && y == m - 1)
return dp[x][y] = 1;
// If reach the corner of the matrix.
if (x == n - 1 || y == m - 1)
result = 1;
// If value greater than below cell.
if (x + 1 < n && mat[x][y] < mat[x + 1][y])
result = 1 + LIP(dp, mat, n, m, x + 1, y);
// If value greater than left cell.
if (y + 1 < m && mat[x][y] < mat[x][y + 1])
result = Math.max(result, 1 + LIP(dp, mat, n, m, x, y + 1));
dp[x][y] = result;
}
return dp[x][y];
}
// Wrapper function
function wrapper(mat, n, m)
{
let dp = new Array(10);
for (let i = 0; i < 10; i++)
{
dp[i] = new Array(10);
for (let j = 0; j < 10; j++)
{
dp[i][j] = -1;
}
}
return LIP(dp, mat, n, m, 0, 0);
}
let mat = [
[ 1, 2, 3, 4 ],
[ 2, 2, 3, 4 ],
[ 3, 2, 3, 4 ],
[ 4, 5, 6, 7 ],
];
let n = 4, m = 4;
document.write(wrapper(mat, n, m));
</script>
7
Complejidad temporal: O(N*M).
Complejidad espacial: O(N*M)
Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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