Unique Paths

Bài toán

Một robot nằm ở góc trên-trái (0, 0) của lưới m x n. Robot chỉ có thể đi Xuống dưới hoặc Sang phải. Hỏi có bao nhiêu đường đi duy nhất để robot đến được góc dưới-phải (m-1, n-1)?

Phân Tích & Tiếp Cận

Grid DP

Gọi dp[i][j] là số cách đi đến ô (i, j). Để đến được (i, j), robot phải đến từ (i-1, j) (ô phía trên) hoặc (i, j-1) (ô bên trái). Công thức: dp[i][j] = dp[i-1][j] + dp[i][j-1]

Base Cases:

• Hàng đầu tiên dp[0][j]: Chỉ có 1 cách (đi thẳng sang phải).
• Cột đầu tiên dp[i][0]: Chỉ có 1 cách (đi thẳng xuống dưới).

function uniquePaths(m: number, n: number): number {
    const dp = Array(m).fill(0).map(() => Array(n).fill(1));

    // Thực tế chỉ cần loop từ 1, vì hàng 0 và cột 0 đã fill 1
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m - 1][n - 1];
}

Toán học (Combinatorics)

Ta cần đi tổng cộng m-1 bước xuống và n-1 bước sang phải. Tổng số bước: (m-1) + (n-1) = m + n - 2. Ta cần chọn m-1 vị trí để đặt bước "Xuống" trong tổng số bước đó. Kết quả = Tổ hợp chập m-1 của m+n-2 ($\binom{m+n-2}{m-1}$).

Pattern Nhận Diện

• Đếm số đường đi trên lưới.
• Có hướng di chuyển hạn chế (Chỉ phải/xuống). -> Grid DP.