ภาพรวมปัญหา
หุ่นยนต์อยู่มุมซ้ายบนของกริด n×m เคลื่อนที่ได้แค่ขวาหรือลง หาจำนวนเส้นทางไปมุมขวาล่าง
ตัวอย่าง
| Robo | ||
| END |
m=3, n=2 → Output: 3 เส้นทาง
อัลกอริทึม (Dynamic Programming)
- สร้างตาราง DP n×m เริ่มต้น -1
- dp[n-2][m-1] = 1
- เติมแถวสุดท้ายและคอลัมน์สุดท้าย = 1
- เติมย้อนกลับ: dp[i][j] = dp[i+1][j] + dp[i][j+1]
- return dp[0][0]
ตัวอย่างโค้ด Python
class Solution(object):
def uniquePaths(self, m, n):
row = n
column = m
dp = [[-1 for i in range(m)] for j in range(n)]
dp[row-2][column-1] = 1
for i in range(column):
dp[n-1][i] = 1
for i in range(row):
dp[i][column-1] = 1
for i in range(row-2, -1, -1):
for j in range(column-2, -1, -1):
dp[i][j] = dp[i+1][j] + dp[i][j+1]
return dp[0][0]
ob1 = Solution()
print(ob1.uniquePaths(10, 3))
Input / Output
Input: 10 3 Output: 55
