Leet Code No.62

I'm not good at dynamic programming. So, I searched for it and wrote about it in this article.

Dynamic programming, short for DP, is the way that decompose big problems into small problems to solve. This is not a concrete algorithm like binary search or Gauss' addition and so on, it's like a method of solving problems.

To understand DP, solve some problems.

Problem

I chose this problem from the leet code.

Solution

The answer will be the total combination of m-1 and n-1. To understand, consider the target grid is 4 x 3.

Let's represent the movement as an arrow.
The robot can move right or down, so the possible moving will be the following:

The robot cannot go back, we just count the sum of the possible paths. To calculate the possible paths, I try to write the number in the grid the possibility. The top row will be 1.

The second and subsequent rows are different, there are multiple paths that exist. The number of possible paths will be the sum of the left grid and the above grid.

To continue this way, we can get the answer. In this case, the answer will be 10.

Write code

I solved this problem with Rust and TypeScript.
The solution is the following:

In Rust:

pub fn unique_paths(m: i32, n: i32) -> i32 {
    let mut grid = vec![vec![1; n as usize]; m as usize];


    for i in 1..(m as usize) {
        for j in 1..(n as usize) {
            grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
        };
    }

    grid[(m - 1) as usize][(n - 1) as usize]
}

In TypeScript:

function uniquePaths(m: number, n: number): number {
    const grid = new Array(m).fill(new Array(n).fill(1));

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
        }
    }

    return grid[m - 1][n - 1]

};

First, create a 2D array filled with 1. The reason for filing with 1 is the top rows and most left columns will be 1 and others are updated during the calculation.

Rust

let mut grid = vec![vec![1; n as usize]; m as usize];

TypeScript

const grid = new Array(m).fill(new Array(n).fill(1));

Then calculate the unique paths. The unique paths are calculated using the left and above cells as it was mentioned above. That is calculated by the loop.

Rust

for i in 1..(m as usize) {
    for j in 1..(n as usize) {
        grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
    };
}

TypeScript

for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
        grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
    }
}

In this way, the unique paths are calculated and the answer will be the most right and bottom cell.