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!