Find minimum cost path javascript

Question

Given a cost matrix cost[][] and a position (m, n) in cost[][], write a function that returns cost of minimum cost path to reach (m, n) from (0, 0). Each cell of the matrix represents a cost to traverse through that cell. The total cost of a path to reach (m, n) is the sum of all the costs on that path (including both source and destination). You can only traverse down, right and diagonally lower cells from a given cell, i.e., from a given cell (i, j), cells (i+1, j), (i, j+1), and (i+1, j+1) can be traversed. You may assume that all costs are positive integers.

For example, in the following figure, what is the minimum cost path to (2, 2)?

The path with minimum cost is highlighted in the following figure. The path is (0, 0) –> (0, 1) –> (1, 2) –> (2, 2). The cost of the path is 8 (1 + 2 + 2 + 3).

function minCost(array, m, n){

    let tc = [m+1][n+1]
    tc[0][0] == array[0][0]

    for (let i = 1; i <= m; i++) {
        tc[i][0] = tc[i-1][0] + cost[i][0]
    }

    for (i = 1; i <= m; i++){
            tc[i][0] = tc[i-1][0] + cost[i][0];
    }
 
        /* Initialize first row of tc array */
    for (j = 1; j <= n; j++){
        tc[0][j] = tc[0][j-1] + cost[0][j];
    }
 
        /* Construct rest of the tc array */
    for (i = 1; i <= m; i++){
        for (j = 1; j <= n; j++){
            tc[i][j] = min(tc[i-1][j-1],tc[i-1][j], tc[i][j-1]) + cost[i][j];
            }
    }
 
        return tc[m][n];
}
console.log(minCost([
    [1,2,3],
    [4,8,2],
    [1, 5, 3]
],2,2))

I facing a problem to solve this algorithm problem. So I tried something but the code got an error. Can anyone identify where is the problem in my code?

user_844416 · Answer

Your code looks almost correct, except for two issues:

using cost array while function argument is array.

Replace cost with array everywhere (but cost name is much better :), so you can replace array with cost)

double filling of the first column

Remove the second for-loop

Find minimum cost path javascript

1 Answers