Các đường dẫn duy nhất trong Python

Giả sử có một rô bốt được đặt ở góc trên bên trái của lưới n x m (n hàng và m cột). Robot chỉ có thể di chuyển bên dưới hoặc bên phải tại bất kỳ thời điểm nào. Robot muốn đến góc dưới cùng bên phải của lưới (được đánh dấu 'KẾT THÚC trong sơ đồ bên dưới). Vậy chúng ta phải tìm xem có bao nhiêu con đường độc đạo khả dĩ? Ví dụ:nếu m =3 và n =2, thì lưới sẽ như dưới đây -

Robo
		HẾT

Đầu ra sẽ là 3, Vì vậy, có tổng cộng 3 cách khác nhau để đạt được từ vị trí bắt đầu đến vị trí cuối cùng. Những con đường này -

Phải → Phải → Xuống
Phải → Xuống → Phải
Xuống → Phải → Phải

Hãy để chúng tôi xem các bước -

Chúng tôi sẽ sử dụng phương pháp lập trình động để giải quyết vấn đề này
let row:=n và col:=m, tạo bảng DP có thứ tự n x m và điền vào giá trị này bằng -1
DP [row - 2, col - 1]:=1
cho tôi trong phạm vi 0 đến col
- DP [n - 1, i]:=1
cho tôi trong phạm vi từ 0 đến hàng
- DP [i, col - 1]:=1
đối với tôi trong phạm vi hàng -2 xuống -1
- cho j trong phạm vi col -2 xuống -1
  - DP [i, j]:=DP [i + 1, j] + DP [i, j + 1]
trả lại DP [0, 0]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

10
3