Đường đi duy nhất trong Python

Giả sử có robot ở góc trên bên trái của lưới n x m (n hàng, m cột). Robot chỉ đi xuống hoặc sang phải. Muốn đến góc dưới bên phải (END). Tìm số đường đi duy nhất. Ví dụ m = 3, n = 2:

Kết quả 3, có 3 cách:

1. Phải → Phải → Xuống
2. Phải → Xuống → Phải
3. Xuống → Phải → Phải

Các bước:

• Dùng quy hoạch động
• row := n, col := m, tạo bảng DP n x m điền -1
• DP[row – 2, col - 1] := 1
• for i in range 0 to col
  • DP[n – 1, i] := 1
• for i in range 0 to row
  • DP[i, col – 1] := 1
• for i in range row -2 down to -1
  • for j in range col -2 down to -1
    • DP[i, j] := DP[i + 1, j] + DP[i, j + 1]
• return DP[0, 0]

Hãy xem triển khai sau:

Ví dụ

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

10 3

Output

55