Learning Journal

2/29/2024

Unique Paths

Tags: algorithms leetcode dynamic_programming

function uniquePaths(m: number, n: number): number {
    const memo:(number|null)[][] = Array(m).fill(0).map(_ => Array(n).fill(null))


    return go(0,0);

    function go (row:number, col:number):number {
        if(row === m - 1 || col === n - 1){
            return 1;
        }
        else if (row >= m || row < 0 || col >= n || col < 0){
            return 0;
        }
        else if(memo[row][col] !== null){
            return memo[row][col];
        }   

        memo[row][col] = go(row, col + 1) + go(row + 1, col);  
        
        return memo[row][col];        
    }

};function uniquePaths(m: number, n: number): number {
    const memo:(number|null)[][] = Array(m).fill(0).map(_ => Array(n).fill(null))


    return go(0,0);

    function go (row:number, col:number):number {
        if(row === m - 1 || col === n - 1){
            return 1;
        }
        else if (row >= m || row < 0 || col >= n || col < 0){
            return 0;
        }
        else if(memo[row][col] !== null){
            return memo[row][col];
        }   

        memo[row][col] = go(row, col + 1) + go(row + 1, col);  
        
        return memo[row][col];        
    }

};

THE PROBLEM

This problem can be solved using dynamic programming as above. In fact, I've gone through 3 iterations to arrive at this solution.

In the first iteration, I used recursion to consider all possible paths and if there is a path that reaches the target, I increase count to 1 unit. However, it took too long to finish. So, in the second iteration, I used dynamic programming to count backward. First, I realize that there is only 1 way to go to the target cell if you start from the last row or the last column. When you start from anywhere else, the total paths that you can go to the target from the current cell equal to the total paths you can go from the right cell plus the total paths you can go from the cell under it. But, it turns out that it also took too long to finish. So, I need to use hash table. The hash table has type like this Record<string,number> with string to be ${row}-{col} and the number to be the number of paths that you can go from there to reach the target. Because I used memo, I don't need to calculate all of the repeated paths anymore. However, it turns out that it' took too long too. So, I looked at the solutions and realized that instead of using the hash table, I can you a 2D array that can store the number or null, it would be much faster. Another interesting thing that I just discovered was that you can calculate how many ways to go from the start to the current cell instead of how many ways to go from the current cell to the target like my approach. The only difference is that I need to return the value at [0][0] while the other approach needs to return the value at [m-1][n-1].

Revised by ChatGPT

This problem can be solved using dynamic programming, I went through three iterations to arrive at the final solution.

First Iteration (Recursion): I used recursion to explore all possible paths, incrementing a count variable whenever a path reached the target. However, this approach was too slow due to the large number of redundant calculations.
Second Iteration (Dynamic Programming - Backward): I realized that there is only one way to reach the target cell from any cell in the last row or column. For other cells, the total number of paths to the target is the sum of the paths from the cell to the right and the cell below. Although this approach reduced the number of calculations, it was still slow.
Third Iteration (Dynamic Programming with Memoization): To further optimize, I initially used a hash table (Record<string,number>) to memorize the number of paths from each cell to avoid redundant calculations. However, this was still not fast enough.
Final Solution (2D Array Memoization): I switched to using a 2D array for memorization, which significantly improved the performance. Additionally, I realized that calculating the number of ways to reach the current cell from the start (instead of from the current cell to the target) was more efficient. The final result is then found at memo[0][0].

This iterative approach not only optimized the solution but also provided valuable insights into problem-solving strategies and the impact of data structures on algorithm performance.