62. Unique Paths
Tags:
Medium
Skills:
DP
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu: Cho một lưới kích thước m x n, một robot bắt đầu ở góc trên bên trái (0,0) và chỉ được di chuyển sang phải hoặc xuống dưới. Hỏi có bao nhiêu cách khác nhau để đi từ (0,0) đến góc dưới bên phải (m-1, n-1)
dp[m][n], trong đó dp[i][j] là số đường đi đến ô (i, j).1function uniquePaths(m: number, n: number): number {
2 const dp: number[][] = Array.from({ length: m }, () => Array(n).fill(1))
3 for (let i = 1; i < m; i++) {
4 for (let j = 1; j < n; j++) {
5 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
6 }
7 }
8 return dp[m - 1][n - 1]
9};1function uniquePaths(m: number, n: number): number {
2 const dp: number[] = Array(n).fill(1);
3
4 for(let i = 1; i < m; i++) {
5 for(let j = 1; j < n; j++) {
6 dp[j] = dp[j] + dp[j - 1];
7 }
8 }
9 return dp[n - 1];
10}