2

I have a matrix like this->

1 6 2
8 3 7
4 9 5

You can go any direction, up down left right diagonally and you have to find the longest sub sequence, you can select a next number in the sequence in such a way that its absolute difference is greater than 3.

Like in the case above the longest sub sequence is 1->6->2->7->3->8->4->9->5.

I am able write a brute force code for it which finds the longest sequence which goes like finding the longest sequence for first number, second number and so on. And return the one which has the largest count.

I am new to DP. Is there any other way to solve this by using DP? I am not able to comprehend a solution using DP.

jbsu32
  • 1,036
  • 1
  • 11
  • 31
Dhananjayan Santhanakrishnan
  • 363
  • 3
  • 22

1 Answers1

3

Let N is the number of rows and M is the number of columns.

You can try dynamic programming approach with a state: dp(int row_idx, int col_idx, int visited_msk) where the visited_msk is an integer representing the visited cells till now (i.e for matrix[i][j] the ID in the visited_msk will be i*M + j

Inside your DP, you will iterate over the neighboring 8 cells (if they are within the boundaries) and call the DP from the current cell only if the absolute difference is more than 3 and the cell is not visited like this:

Let the new index in the mask is new_idx = new_row_idx * M + new_col_idx in the internal loop, then the condition will be something like this:

if(abs(matrix[row_idx][col_idx] - matrix[new_row_idx][new_col_idx]) > 3 && !((visited_msk >> new_idx) & 1)) {
  result = max(result, dp(new_row_idx, new_col_idx, visited_msk | (1<<new_idx)) + 1);
}

The order of this approach is O(2^(N*M) * N * M * 8), so it will be fine if N*M (the grid size) is <= 15.

khairy
  • 116
  • 3
  • Can you please elaborate the answer a bit? I couldn't get you – Dhananjayan Santhanakrishnan Mar 21 '17 at 08:39
  • The visited_msk will be an integer, and should I keep a list of visited_msk to keep track of visited items for a particular iteration? As I finish visiting all the paths possible for the particular element I find the maximum and remove the visited_msk of that element from the list continuing it with the next element. – Dhananjayan Santhanakrishnan Mar 21 '17 at 09:07
  • 1
    `visited_msk` is ordinary integer, but we'll deal with it as bool array. 'signed int' in programming languages consists of 32 bits (1 bit for sign). e.g: 5 is represented as 101 So, if you treated the int as array, 5 is an array where elements 0 and 2 are set with 1(visited) and other bits are not, and if you want to set a bit with index 3 to 1 you need to do this `(0101 | 1000) = 1101`,which means ORing 5 with 8 i.e `5 | (1<<3)` -> `msk | (1<>idx)&1)` checks if bit is set to 1 or 0. For more about bitmasks http://stackoverflow.com/questions/10493411/what-is-bit-masking – khairy Mar 22 '17 at 15:53