# Find best sequences of moves in matrix using Dynamic Programming

I tried to write a dynamic program to solve the following problem.

Given a $$n \times m$$ matrix $$A$$, select a one element per row in order to maximize the following measure $$m$$:

• Each selected element $$a_{i,j}$$ that is on the last row $$(i=n)$$ or directly above the element $$a_{i-1,j}$$ selected in the previous row contributes $$a_{i,j}$$ to $$m$$.
• Each element $$a_{i,j}$$ that is not on the last row and not directly above the element selected in the previous row contributes $$-a_{i,j}$$ to $$m$$.

For example:

Matrix: $$\begin{bmatrix} 4 & 9 & 4 \ 3 & 1 & 2 \ 3 & 5 & 8 \ \end{bmatrix}$$

Output: 16 (8 – 1 + 9) (From bottom row to top)

Another example:

Grid:

$$\begin{bmatrix} 9 & 2 & 1 & 3 \ 3 & 7 & 6 & 1 \ 1 & 2 & 3 & 9 \end{bmatrix}$$

Output: 15 (9 – 3 + 9) (From bottom row to top)

My idea is to compare between 3+3+4 and 3-1+9 and 3-2+4 and so on.

Here is my method of doing it:

int row, col; int max_score(vector<vector<int> > grid, int r, int c) {     int result = 0;     if(c > 0 && c < col - 1 && r > 0) {         result = max_score(grid, r-1, c) + grid[r-1][c];         result = max(result, max_score(grid, r-1, c-1) - grid[r-1][c-1]);         result = max(result, max_score(grid, r-1, c+1) - grid[r-1][c+1]);     }     else if(c == 0 && r > 0) {         result = max_score(grid, r-1, c) + grid[r-1][c];         result = max(result, max_score(grid, r-1, c+1) - grid[r-1][c+1]);     }     else if(c == col - 1 && r > 0) {         result = max_score(grid, r-1, c) + grid[r-1][c];         result = max(result, max_score(grid, r-1, c-1) - grid[r-1][c-1]);     }     return result; }  int main() {     int a, result;     cin >> row >> col;     vector<vector<int> > grid( row , vector<int> (col));        for (int i = 0; i < row; i++) {          for (int j = 0; j < col; j++){              cin >> a;             grid[i][j] = a;          }      }       for(int i = row - 1; i > 0; i--) {         for(int j = 0; j < col; j++) {             result = max_score(grid, i, j);         }     }      cout << result << endl;     return 0; } 

I was getting the wrong result of this. Any suggestion will help. Thank you!