DEV Community

hirohata
hirohata

Posted on • Updated on

Leet Code No.62

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:

Image description

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.

Image description

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.

Image description

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

Image description

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]
}
Enter fullscreen mode Exit fullscreen mode

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]

};
Enter fullscreen mode Exit fullscreen mode

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];
Enter fullscreen mode Exit fullscreen mode

TypeScript

const grid = new Array(m).fill(new Array(n).fill(1));
Enter fullscreen mode Exit fullscreen mode

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];
    };
}
Enter fullscreen mode Exit fullscreen mode

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];
    }
}
Enter fullscreen mode Exit fullscreen mode

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

Top comments (0)