Number of paths to reach last cell

Given a (n,n) 2D matrix and a total cost to reach the destination cell, we need to start from (0,0) cell and go till (n-1,n-1) cell. Assuming that each cell has a cost associated and we can only go right or down from current cell. Find the number of ways to reach destination cell with given total cost.

Example
-----------
input: [
  [ 4, 7, 1, 6 ],
  [ 5, 7, 3, 9 ],
  [ 3, 2, 1, 2 ],
  [ 7, 1, 6, 3 ]
]
cost: 25
output: 2
Explanation: 4->7->1->3->1->6->3 and 4->5->7->4->1->2->3

Solution

This problem can be solved by applying Divide and Conquer to break down the problem into smaller subproblems. Thus, by solving these subproblems, we will arrive at our final answer. Let’s try to derive the subproblems.

1. f(2, 3, 22) -> e.g. 5 ways ---|---sum
2. f(3, 2, 22) -> e.g. 4 ways ---|

We shall start by looking at the last cell. In order to reach the last cell, we know that the traversal can only go right or down. Therefore, it meant that from the last cell, we can only go left or up. If the given cost is 25, we know that in order to reach the last cell which has a value of 3, the cell before need to only have a value of 22. Hence, if we can solve these, by summing them up we can then get our final answer.

Code Algortihm

function numPaths(mat: number[][], row: number, col: number, cost: number): number {
  if (cost < 0) return 0;

  remainingCost = cost - mat[row][col];

  if (row === 0 && col === 0) {
    return remainingCost === 0 ? 1: 0;
  }

  if (row === 0) {
    return numPaths(mat, 0, col - 1, remainingCost);
  }

  if (col === 0) {
    return numPaths(mat, row - 1, 0, remainingCost);
  }

  const fromUp = numPaths(mat, row - 1, col, remainingCost);
  const fromLeft = numPaths(mat, row, col - 1, remainingCost);

  return fromUp + fromLeft;
}

Optimisation

Let’s look at the an example of the recursion tree see if we need to optimise this solution.

                                   p(3,3,25)
                                  /          \
                              /                \
                          /                      \
                      p(2,3,22)                  p(3,2,22)
                    /        \                  /       \
                  /             \           p(2,2,20)   p(3,1,20)
            p(1,3,20)         p(2,2,20)     /      \
            /         \                 p(1,2,19) p(2,1,19)
          /             \
      p(0,3,11)       p(1,2,11)
      |               /        \
      |-p(0,2,5)   p(0,2,8)   p(1,1,8)
      |-p(0,3,4)   |
                   |-p(0,1,7)

We are computing a new of the subproblems more than once such as p(2,2,20). We can then apply Dynamic Programming to optimise the solution.

type HashTable = {
  [x: number]: {
    [y: number]: {
      [z: number]: number;
    };
  };
};

const dp: HashTable = {};

function numPaths(mat: number[][], row: number, col: number, cost: number): number {
  if (cost < 0) return 0;

  remainingCost = cost - mat[row][col];

  if (row === 0 && col === 0) {
    return remainingCost === 0 ? 1: 0;
  }

  if (!(row in dp)) {
    dp[row] = {};
  }

  if (!(col in dp)) {
    dp[col] = {};
  }

  if (!(cost in dp[row][col])) {
    if (row === 0) {
      dp[row][col][cost] = numPaths(mat, 0, col - 1, remainingCost);
    } else if (col === 0) {
      dp[row][col][cost] = numPaths(mat, row - 1, 0, remainingCost);
    } else {
      const fromUp = numPaths(mat, row - 1, col, remainingCost);
      const fromLeft = numPaths(mat, row, col - 1, remainingCost);
      dp[row][col][cost] = fromUp + fromLeft;
    }
  }

  return dp[row][col][cost];
}

Bottom Up Approach

We can now then apply some reverse engineer to use the Bottom Up Approach (also known as Tabulation). Firstly, let’s start from looking at the Top Down Approach using a matrix table.

For our top down approach, in order to get the solution at R1C1, we entered from R4C4 and worked our way up, checking the cost as we go along. Hence, in order to perform bottom up approach. However, this is a tricky scenario because typically at our base condition, we have a value, instead, at R1C1 we are dependent on the other cells for the remaining cost. Hence, we will need to apply the same format, starting from the bottom and working our way up to R1C1 with a twist. I will cover it in the next time as it is going to be long post by itself.