Giả sử chúng ta có một mảng 2D kích thước m × n. Một người bắt đầu ở ô bắt đầu (0,0) và muốn đến ô kết thúc (m, n). Hạn chế là tại một thời điểm, người đó chỉ có thể di chuyển một bước xuống hoặc một bước sang phải.
Chúng ta cần viết một hàm JavaScript nhận vào chiều cao và chiều rộng của lưới 2D.
Hàm nên tìm ra số lượng đường đi duy nhất có sẵn cho người đó để đến đích.
Ví dụ
Dưới đây là mã nguồn:
const height = 3; const width = 4; const findUniquePath = (width = 1, height = 1) => { const board = Array(height).fill(null).map(() => { return Array(width).fill(0); }); for (let rowIndex = 0; rowIndex < height; rowIndex += 1) { for (let columnIndex = 0; columnIndex < width; columnIndex += 1) { if (rowIndex === 0 || columnIndex === 0) { board[rowIndex][columnIndex] = 1; } } } for (let rowIndex = 1; rowIndex < height; rowIndex += 1) { for (let columnIndex = 1; columnIndex < width; columnIndex += 1) { const uniquesFromTop = board[rowIndex - 1][columnIndex]; const uniquesFromLeft = board[rowIndex][columnIndex - 1]; board[rowIndex][columnIndex] = uniquesFromTop + uniquesFromLeft; } } return board[height - 1][width - 1]; }; console.log(findUniquePath(width, height));Kết quả
Đầu ra trên console:
10
Giải thích: Đây là bài toán kinh điển "Unique Paths" (LeetCode 62). Số đường đi = C(m+n-2, m-1) = tổ hợp. Giải pháp DP O(m*n) như code, có thể tối ưu thành O(min(m,n)) không gian hoặc O(1) dùng công thức tổ hợp.