Tukukkk

Given a 2d grid, with the below constraints, I want to find the longest sub-sequence :

1. allowed to move up, right, left, down, diagonally


2. difference between the current value and the next value should be greater than or equal to 3 (i.e absolute difference).


3. visited cells should not be repeated


4. grid could be maximum 10 x 10


5. not allowed to do 4 -> 9 in the below example

Example:

824

061

379

The length of the longest path for the above input is 8, with the sequence 9,1,6,2,8,0,7,3

I tired to approach using multiple for loops, but it would be highly inefficient. I want to know how do I approach using Dynamic Programming. Any help would be appreciated.

Just run bfs (Breadth-first search) from every possible source in the grid by following the constraints. For example, in your given sample input the number of possible source is 9. Then, save the paths in some suitable data structure. After saving the paths, check which path is longest and that's your answer.

I could find the longest increasing sub-sequence. Can someone suggest, how do I accomodate the condition "difference between the current value and the next value should be greater than or equal to 3" ?. The code below takes care of just an increasing sequence.

public class Test {

public static void main(String args) {



    int matrix = {{1,2,3}, {2,4,2}, { 5,6,7}};

    System.out.println(new Test().longestIncreasingPaths(matrix));



}



public int longestIncreasingPaths(int matrix) {



    if (matrix == null || matrix.length < 1 || matrix[0].length < 1)

        return 0;



    int max = 0, n = matrix.length, m = matrix[0].length;



    int cache = new int[n][m];



    for (int i = 0; i < n; i++) {

        for (int j = 0; j < m; j++) {

            max = Math.max(dfs(matrix, Integer.MIN_VALUE, i, j, n, m, cache), max);

        }

    }

    return max;

}



int dfs(int matrix, int min, int i, int j, int n, int m, int cache) {



    if (i < 0 || j < 0 || i >= n || j >= m)

        return 0;



    if (matrix[i][j] <= min)

        return 0;



    if (cache[i][j] != 0)

        return cache[i][j];



    min = matrix[i][j];



    int a = dfs(matrix, min, i - 1, j, n, m, cache) + 1;

    int b = dfs(matrix, min, i + 1, j, n, m, cache) + 1;

    int c = dfs(matrix, min, i, j - 1, n, m, cache) + 1;

    int d = dfs(matrix, min, i, j + 1, n, m, cache) + 1;

    int e = dfs(matrix, min, i+1, j + 1, n, m, cache) + 1;

    int f = dfs(matrix, min, i - 1, j - 1, n, m, cache) + 1;

    int g = dfs(matrix, min, i + 1, j - 1, n, m, cache) + 1;

    int h = dfs(matrix, min, i - 1, j + 1, n, m, cache) + 1;



    int max = Math.max(a, Math.max(b, Math.max(c, Math.max(d, Math.max(e, Math.max(f, Math.max(g,h)))))));

    cache[i][j] = max;



    return max;

}

}