Leet Code No.62
Published: 2023-10-04 20:50:48

# 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](https://leetcode.com/problems/unique-paths/) 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8zcn0q9qkbl2jdhzg0ge.png)

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xe20xqc0j6p182x1ely4.png)

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/miva6sb38vxb8nl8lcsw.png)

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/doq7qe36fossf3r06op3.png)

### Write code

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

In Rust:

```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:

```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

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

TypeScript

```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

```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

```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.