โปรแกรมนับจำนวนวิธีที่ลูกบอลสามารถหล่นลงสู่ระดับต่ำสุดโดยหลีกเลี่ยงขั้นตอนที่ขึ้นบัญชีดำใน Python

สมมติว่าเรามีค่า h และรายการตัวเลขที่เรียกว่าบัญชีดำ ขณะนี้เราอยู่ที่ความสูง h และกำลังเล่นเกมที่จะย้ายลูกบอลขนาดเล็กลงไปที่ความสูง 0 ในตอนนี้ ในรอบที่เท่ากัน (เริ่มจาก 0) เราสามารถเคลื่อนลูกบอล 1, 2 หรือ 4 บันไดลงได้ และในรอบคี่ เราสามารถเคลื่อนลูกบอล 1, 3 หรือ 4 ขั้นลงไปได้ บางระดับถูกขึ้นบัญชีดำ ดังนั้นถ้าบอลไปถึงที่นั่นก็จะตายทันที เราต้องหาจำนวนวิธีที่ลูกบอลสามารถเคลื่อนที่ลงมาที่ความสูง 0 ได้ หากคำตอบมีขนาดใหญ่เกินไป ให้ปรับผลลัพธ์เป็น 10^9 + 7

ดังนั้น หากอินพุตเป็นเหมือน h =5 blacklist =[2, 1] ผลลัพธ์จะเป็น 2 เพราะในรอบที่ 0 ให้ย้ายหนึ่งขั้นตอนก่อน (5 ถึง 4) จากนั้นในรอบถัดไปจาก 4 เป็น 0 อีกวิธีที่เป็นไปได้คือรอบที่ 0 เลื่อนสองขั้นตอน (5 ถึง 3) จากนั้นในรอบที่ 3 เป็น 0

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• บัญชีดำ :=ชุดใหม่จากองค์ประกอบของบัญชีดำ
• ถ้า 0 อยู่ในบัญชีดำหรือ h อยู่ในบัญชีดำ ดังนั้น
  • คืน 0
• dp :=รายการขนาด h และภายในที่เก็บคู่ [0, 0] ที่แต่ละดัชนี
• dp[0] :=[1, 1]
• ม :=10^9 + 7
• สำหรับฉันในช่วง 1 ถึง h ทำ
  • สำหรับแต่ละ x ใน [1, 2, 3, 4] ทำ
    • ถ้า i - x>=0 และ i - x ไม่อยู่ใน blacklist แล้ว
      • ถ้า x ไม่เหมือนกับ 3 แล้ว
        • dp[i, 0] :=dp[i, 0] + dp[i - x, 1]
      • ถ้า x ไม่เหมือนกับ 2 แล้ว
        • dp[i, 1] :=dp[i, 1] + dp[i - x, 0]
    • dp[i, 0] :=dp[i, 0] mod m
    • dp[i, 1] :=dp[i, 1] mod m
• ผลตอบแทน dp[h, 0]

ตัวอย่าง

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

defแก้ปัญหา(h, blacklist):blacklist =set(blacklist) if 0 in blacklist or h in blacklist:return 0 dp =[[0, 0] for i in range(h + 1)] dp[0] =[1, 1] m =10 ** 9 + 7 for i in range(1, h + 1):for x in [1, 2, 3, 4]:if i - x>=0 and i - x ไม่อยู่ในบัญชีดำ:if x !=3:dp[i][0] +=dp[i - x][1] if x !=2:dp[i][1] +=dp[i - x][ 0] dp[i][0] %=m dp[i][1] %=m return dp[h][0]h =5blacklist =[2, 1]print(solve(h, blacklist)) 
อินพุต
 
5, [2, 1]
 
ผลลัพธ์
 
2