เส้นทางที่ไม่ซ้ำใน Python

สมมติว่ามีหุ่นยนต์อยู่ที่มุมบนซ้ายของตารางขนาด n x m (แถว n และคอลัมน์ m) หุ่นยนต์สามารถเคลื่อนที่ได้ทั้งด้านล่างหรือด้านขวาเมื่อใดก็ได้ หุ่นยนต์ต้องการไปถึงมุมล่างขวาของตาราง (ทำเครื่องหมาย 'END ในแผนภาพด้านล่าง) ดังนั้นเราต้องค้นหาว่ามีเส้นทางที่ไม่ซ้ำกันกี่เส้นทาง? ตัวอย่างเช่น ถ้า m =3 และ n =2 ตารางจะเป็นดังนี้ −

ผลลัพธ์จะเป็น 3 ดังนั้นจึงมีทั้งหมด 3 วิธีในการเข้าถึงจากตำแหน่งเริ่มต้นไปยังตำแหน่งสิ้นสุด เส้นทางเหล่านี้คือ −

1. ขวา → ขวา → ลง
2. ขวา → ล่าง → ขวา
3. ลง → ขวา → ขวา

ให้เราดูขั้นตอน -

• เราจะใช้วิธีการเขียนโปรแกรมแบบไดนามิกเพื่อแก้ปัญหานี้
• ให้แถว :=n และ col :=m สร้างตาราง DP ของคำสั่ง n x m แล้วเติมด้วย -1
• DP[row – 2, col - 1] :=1
• สำหรับฉันอยู่ในช่วง 0 ถึง col
  • DP[n – 1, i] :=1
• สำหรับฉันอยู่ในช่วง 0 ถึงแถว
  • DP[i, col – 1] :=1
• สำหรับฉันอยู่ในช่วงแถว -2 ลงไปที่ -1
  • สำหรับ j ในช่วง col -2 ลงไป -1
    • DP[i, j] :=DP[i + 1, j] + DP[i, j + 1]
• คืน DP[0, 0]

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

อินพุต

10
3

ผลลัพธ์

55