Oleksii Trekhleb | Javascript algorithms (Unique Paths Problem)

This is a series of books diving deep into the core mechanisms of the JavaScript language.

 · 3 phút đọc.

This is a series of books diving deep into the core mechanisms of the JavaScript language.

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Unique Paths

Examples

Example #1

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example #2

Input: m = 7, n = 3
Output: 28

Algorithms

Backtracking

First thought that might came to mind is that we need to build a decision tree where D means moving down and R means moving right. For example in case of boars width = 3 and height = 2 we will have the following decision tree:

START
/   \
D     R
/     /   \
R      D      R
/      /         \
R      R            D

END    END          END

We can see three unique branches here that is the answer to our problem.

Time Complexity: O(2 ^ n) - roughly in worst case with square board of size n.

Auxiliary Space Complexity: O(m + n) - since we need to store current path with positions.

Dynamic Programming

Let’s treat BOARD[i][j] as our sub-problem.

Since we have restriction of moving only to the right and down we might say that number of unique paths to the current cell is a sum of numbers of unique paths to the cell above the current one and to the cell to the left of current one.

BOARD[i][j] = BOARD[i   - 1][j] + BOARD[i][j   - 1]; // since we can only move down or right.

Base cases are:

BOARD[0][any] = 1; // only one way to reach any top slot.
BOARD[any][0] = 1; // only one way to reach any slot in the leftmost column.

For the board 3 x 2 our dynamic programming matrix will look like:

011
0011
1123

Each cell contains the number of unique paths to it. We need the bottom right one with number 3.

Time Complexity: O(m n) - since we’re going through each cell of the DP matrix.

Auxiliary Space Complexity: O(m n) - since we need to have DP matrix.

Pascal’s Triangle Based

This question is actually another form of Pascal Triangle.

The corner of this rectangle is at m + n - 2 line, and at min(m, n) - 1 position of the Pascal’s Triangle.

nhavantuonglai

Share:
Quay lại.

Có thể bạn chưa đọc

Xem tất cả »
Tối ưu nội dung

Tối ưu nội dung

Giúp Google và người dùng tìm thấy nội dung website hướng dẫn nâng cao những kỹ thuật giúp tối ưu SEO hiệu quả đem lại thứ hạng tốt trên công…

Tại sao giải pháp cần làm website?

Tại sao giải pháp cần làm website?

Chuỗi bài viết về kiến thức kinh doanh vàng bạc đá quý quỹ ủy thác đầu tư do nhavantuonglai chia sẻ sẽ cung cấp những kiến thức hữu ích giúp…

Đăng ký nhận bảng tin hàng tuần

Liên lạc trao đổi

Liên lạc thông qua Instagram

Thông qua Instagram, bạn có thể trao đổi trực tiếp và tức thời, cũng như cập nhật những thông tin mới nhất từ nhavantuonglai.

Tức thời

Bạn có thể gửi và nhận tin nhắn nhanh chóng, trực tiếp, giúp những vấn đề cá nhân của bạn được giải quyết tức thời và hiệu quả hơn.

Thân thiện

Vì tính chất là kênh liên lạc nhanh, nên bạn có thể bỏ qua những nghi thức giao tiếp thông thường, chỉ cần lịch sự và tôn trọng thì sẽ nhận được sự phản hồi đầy thân thiện, thoải mái từ tác giả.

Trao đổi trên email

Thông qua email cá nhân, bạn có thể trao đổi thỏa thuận hợp tác, kết nối chuyên sâu và mang tính chuyên nghiệp.

Tin cậy

Trong một số trường hợp, email được dùng như một tài liệu pháp lý, chính vì vậy mà bạn có thể an tâm và tin cậy khi trao đổi với tác giả thông qua email.

Chuyên nghiệp

Cấu trúc của email đặt tính chuyên nghiệp lên hàng đầu, nên những thông tin, nội dung được viết trong email từ tác giả sẽ luôn đảm bảo điều này ở mức cao nhất.