62. Unique Paths

Giới thiệu bài toán

Chi tiết: https://leetcode.com/problems/unique-paths/

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Yêu cầu

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 10^9.

Giải quyết bài toán

Ta lập bảng 2 chiều m x n để lưu số lượng đường đi tại mỗi ô.

Dễ dàng nhận thấy, số lượng đường đi tại ô (i, j) bằng tổng số lượng đường đi tại ô (i - 1, j) và (i, j - 1). Trong đó, ô (i - 1, j) là ô phía trên ô (i, j) và ô (i, j - 1) là ô bên trái ô (i, j).

Lưu ý, ô (i, j) nếu nằm ở hàng đầu tiên hoặc cột đầu tiên thì số lượng đường đi tại ô đó luôn bằng 1.

	1	2	3	4	5	6	7	8	y
1	0	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8
3	1	3	6	10	15	21	28
4	1	4	10	20	35	56
5	1	5	15	35	70
x	1								value

C#

public class Solution {
    public int UniquePaths(int m, int n) {
        var A = new int[m, n];
        for (int i = 0; i < m; i++) {
            A[i, 0] = 1;
        }
        for (int j = 0; j < n; j++) {
            A[0, j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                A[i, j] = A[i - 1, j] + A[i, j - 1];
            }
        }
        return A[m - 1, n - 1];
    }
}

TypeScript

function uniquePaths(m: number, n: number): number {
    var A : number[][] = Array.from(Array(m), _ => Array(n).fill(0));

    for (var i = 0; i < m; i++) {
            A[i][0] = 1;
        }
    for (var j = 0; j < n; j++) {
        A[0][j] = 1;
    }
    for (var i = 1; i < m; i++) {
        for (var j = 1; j < n; j++) {
            A[i][j] = A[i-1][j] + A[i][j-1];
        }
    }
    return A[m-1][n-1];
};

Tham khảo:

• C#
• TypeScript