Min cost to reach last cell in 2D Array

Given a (n,n) 2D matrix, 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 traversal in minimum cost.

Example
-----------
input: [
  [ 4, 7, 8, 6, 4 ],
  [ 6, 7, 3, 9, 2 ],
  [ 3, 8, 1, 2, 4 ],
  [ 7, 1, 7, 3, 7 ],
  [ 2, 9, 8, 9, 3 ]
]
output: 36
Explanation: 4->6->7->3->1->2->3->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. min of going right f(0, 1) and going down f(1, 0)
2. if we reach the end of the right cell, we can only go down
3. if we reach the end of the bottom cell, we can only go right

Code Algortihm

function minCost(mat: number[][], row: number, col: number): number {
  if (row > mat.length - 1 || col > mat[0].length - 1) return Number.MAX_SAFE_INTEGER;
  if (row === mat.length -1 && col === mat[0].length - 1) return mat[row][col];

  const right = minCost(mat, row, col + 1);
  const down = minCost(mat, row + 1, col);

  return mat[row][col] + Math.min(right, down);
}

Optimisation

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

                                    min(0,0)
                                  /          \
                              /                \
                          /                      \
                      min(0,1)                   min(1,0)
                    /        \                  /       \
                  /             \           min(1,1)     min(2,0)
              min(0,2)         min(1,1)     /      \
            /         \                 min(1,2)  min(2,1)
          /             \
        min(0,3)       min(1,2)
      /       \        /       \
min(0,4)   min(1,3)  min(1,3)  min(2,2)

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

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

const dp: HashTable = {};

function minCost(mat: number[][], row: number, col: number): number {
  if (row > mat.length - 1 || col > mat[0].length - 1) return Number.MAX_SAFE_INTEGER;
  if (row === mat.length -1 && col === mat[0].length - 1) return mat[row][col];
  if (!(row in dp)) {
    dp[row] = {};
  }

  if (!(col in dp[row])) {
    const right = minCost(mat, row, col + 1);
    const down = minCost(mat, row + 1, col);

    dp[row][col] = mat[row][col] + Math.min(right, down);
  }

  return dp[row][col];
}

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 top down approach, we enter from R1C1 and then recusively all the way to R5C5 to hit our base condition which is the first independent value. Hence, for bottom up approach, we can the solve R5C5 cell first, then the R5 row and then make our way up to R1C1 to get our final answer.

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

function minCost(mat: number[][]): number {
  const dp: HashTable = {};

  for (let row = mat.length - 1; row > -1; --row) {
    for (let col = mat.length - 1; col > -1; --col) {
      if (!(row in dp)) {
        dp[row] = {};
      }

      if (row === mat.length - 1 && col === mat[0].length - 1) {
        dp[row][col] = mat[row][col];
      } else if (row === mat.length - 1) {
        dp[row][col] = mat[row][col] + dp[row][col + 1];
      } else if (col === mat[0].length - 1) {
        dp[row][col] = mat[row][col] + dp[row + 1][col];
      } else {
        dp[row][col] = mat[row][col] + Math.min(dp[row + 1][col], dp[row][col + 1]);
      }
    }
  }

  return dp[0][0];
}