หาจำนวน Unique Paths ในกริด 2D ด้วย JavaScript

ปัญหา Unique Paths

กริดขนาด m × n เริ่มที่ (0,0) ไปถึง (m-1, n-1) เดินได้เฉพาะ ขวา หรือ ล่าง หาจำนวนเส้นทางที่เป็นไปได้

ตัวอย่าง

Grid 3×4 (height=3, width=4) → 10 paths

โค้ดตัวอย่าง (Dynamic Programming - Bottom Up)

const height = 3;
const width = 4;

const findUniquePath = (width = 1, height = 1) => {
  // สร้าง board: board[row][col] = จำนวนวิธีไปถึงจุดนี้
  const board = Array(height).fill(null).map(() => 
    Array(width).fill(0));
  
  // Base case: แถวแรกและคอลัมน์แรก = 1 วิธี (เดินตรง)
  for (let rowIndex = 0; rowIndex < height; rowIndex++) {
    for (let colIndex = 0; colIndex < width; colIndex++) {
      if (rowIndex === 0 || colIndex === 0) {
        board[rowIndex][colIndex] = 1;
      }
    }
  }
  
  // Fill DP table
  for (let rowIndex = 1; rowIndex < height; rowIndex++) {
    for (let colIndex = 1; colIndex < width; colIndex++) {
      const fromTop = board[rowIndex - 1][colIndex];
      const fromLeft = board[rowIndex][colIndex - 1];
      board[rowIndex][colIndex] = fromTop + fromLeft;
    }
  }
  
  return board[height - 1][width - 1];
};

console.log(findUniquePath(width, height));

ผลลัพธ์

10

สูตรคณิตศาสตร์ (Combinatorics) - O(1) Space

จำนวนเส้นทาง = C(m+n-2, m-1) = (m+n-2)! / ((m-1)! × (n-1)!)

const uniquePathsMath = (m, n) => {
  // คำนวณ C(m+n-2, min(m,n)-1) เพื่อลดการคำนวณ
  let total = m + n - 2;
  let choose = Math.min(m, n) - 1;
  let result = 1;
  
  for (let i = 1; i <= choose; i++) {
    result = result * (total - choose + i) / i;
  }
  return Math.round(result);
};

console.log(uniquePathsMath(3, 4)); // 10
console.log(uniquePathsMath(100, 100)); // 22750883079422934966181954039568885395604168260154104734000

เวอร์ชัน Space Optimized (O(n) Space)

const uniquePathsOptimized = (m, n) => {
  const dp = new Array(n).fill(1); // แถวแรก = 1 ทุกคอลัมน์
  
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[j] += dp[j - 1];
    }
  }
  return dp[n - 1];
};

ขยาย: Unique Paths II (มีอุปสรรค)

const uniquePathsWithObstacles = (grid) => {
  const m = grid.length, n = grid[0].length;
  const dp = new Array(n).fill(0);
  dp[0] = grid[0][0] === 0 ? 1 : 0;
  
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) dp[j] = 0; // อุปสรรค
      else if (j > 0) dp[j] += dp[j - 1];
    }
  }
  return dp[n - 1];
};

สรุป

• DP 2D Array - เข้าใจง่าย O(m×n) Space
• DP 1D Array - ประหยัดหน่วยความจำ O(n) Space
• Math Formula - เร็วที่สุด O(min(m,n)) Time, O(1) Space