Dynamic Programming find max path with constraints in 2D array

Question

Hi I have a question in dp which goes like this:

Input: 2D Array of numbers

Output: The maximum sum of a path that goes from (0,0) to (n-1,n-1) Where these two conditions need to be met:

1. You can only move down and right meaning:

   (A[i-1][j]) --> (A[i][j]) or (A[i][j-1]) --> (A[i][j])

2. You cannot move three times horizontally in one row

My code so far:

export default (arr: Array<Array<number>>) => {

    let B: Array<Array<{ info: number, rightCount: number }>> = init2DArr(arr.length, arr[0].length) // when 
    B[0][0] = { info: arr[0][0], rightCount: 0 };

    for (let i = 1; i < arr.length; i++) {
        B[0][i] = { info: (arr[0][i] + B[0][i - 1].info), rightCount: i };
        B[i][0] = { info: (arr[i][0] + B[i - 1][0].info), rightCount: 0 };
    }
    for (let i = 1; i < arr.length; i++) {
        for (let j = 1; j < arr.length; j++) {
            if(B[i-1][j].rightCount >= 3){
                B[i][j] = { info: arr[i][j] + B[i][j - 1].info, rightCount: B[i][j - 1].rightCount + 1 }
                continue;
            }

            if(B[i][j-1].rightCount == 2){
                B[i][j] = { info: arr[i][j] + B[i - 1][j].info, rightCount: 0 }
                continue;
            }

            if (B[i - 1][j].info >= B[i][j - 1].info) { // top
                B[i][j] = { info: arr[i][j] + B[i - 1][j].info, rightCount: 0 }
            }
            else if(B[i][j-1].info > B[i-1][j].info)
            {
                B[i][j] = { info: arr[i][j] + B[i][j - 1].info, rightCount: B[i][j - 1].rightCount + 1 }
            }
        }
    }
    console.log(B[arr.length - 1][arr.length - 1].info)
}



const init2DArr = (n: number, m: number) => {
    let res = Array(n);
    for (let i = 0; i < res.length; i++) {
        res[i] = Array(m)
    }
    return res;
}

But this code is not complete because for this input:

getMaxPath([[1,1,1,1],
            [7,9,4,2000],
            [6,22,1,1],
            [1,1,1,1]])

2000 is not included in the path even though the path:

1 -> 1 -> 9 -> 4 -> 2000 -> 1 -> 1

is clearly the maximum.

Therefore the code should return 2017 (the sum of the path).

Meaning my code is not taking in evaluation all the possible paths. Any help would be appreciated

Answer 1

Here an implementation with dynamic programming, it processes each row exploring the maximum value that can be reached on a cell moving horizontally before going down.

<script>
  function getMaxPath(arr) {
    var currentRow = [{
      sum: 0,
      path: []
    }];
    for (var i = 0; i < arr.length; i++) {
      var row = arr[i];
      var nextRow = new Array();
      for (var j = 0; j < currentRow.length; j++) {
        var sum = currentRow[j].sum;
        var path = currentRow[j].path.slice();
        for (var k = 0; k <= 2 && j + k < row.length; k++) {
          sum += row[j + k];
          path.push(row[j + k]);
          if (j + k >= nextRow.length) {
            nextRow.push({ sum: sum, path: path.slice() });
          } else {
            if (sum > nextRow[j + k].sum) {
              nextRow[j + k] = { sum: sum, path: path.slice() };
            }
          }
        }
      }
      currentRow = nextRow;
    }
    return currentRow[currentRow.length - 1];
  }
  console.log(getMaxPath([
    [1, 1, 1, 1],
    [7, 9, 4, 2000],
    [6, 22, 1, 1],
    [1, 1, 1, 1]
  ]));
</script>

Answer 2

A typical bottom-up dynamic program would use a third state in addition to i and j here. Like [i][j][num_moves], doubling the space requirement. But your code doesn't allow for multiple, simultaneous move-count states for each (i, j) combination. Try to formulate the recurrence using dp[i][j][num_moves].

Answer 3

You could take a brute force approach and get all possible and valid pathes and take the one with the greatest sum.

function getMaxPath(matrix) {
    const
        sum = array => array.reduce((a, b) => a + b),
        stack = [[0, 0, '', 0, []]],
        pathes = [];

    while (stack.length) {
        const [i, j, dir, count, [...path]] = stack.shift();
        path.push(matrix[i][j]);
        if (i === matrix.length - 1 && j === matrix[i].length - 1) {
            pathes.push(path);
            continue;
         }
        
        if (i + 1 < matrix.length && (dir !== 'down' || count < 2)) {
            stack.push([i + 1, j, 'down', dir === 'down' ? count + 1 : 1, path]);
        }
        
        if (j + 1 < matrix[i].length && (dir !== 'right' || count < 2)) {
            stack.push([i, j + 1, 'right', dir === 'right' ? count + 1 : 1, path]);
        }
    }
    return pathes.reduce((a, b) => sum(a) > sum(b) ? a : b);
}

console.log(...getMaxPath([[1, 1, 1, 1], [7, 9, 4, 2000], [6, 22, 1, 1], [1, 1, 1, 1]]));