Chương trình đếm số cách quả bóng có thể giảm xuống mức thấp nhất bằng cách tránh các bước trong danh sách đen trong Python

Giả sử chúng ta có một giá trị h và một danh sách các số được gọi là danh sách đen. Hiện tại chúng ta đang ở độ cao h và đang chơi trò chơi di chuyển một quả bóng nhỏ xuống độ cao 0. Bây giờ, trong các vòng chẵn (bắt đầu từ 0), chúng ta có thể di chuyển quả bóng 1, 2 hoặc 4 cầu thang xuống. Và trong các vòng lẻ, chúng ta có thể di chuyển bóng 1, 3, hoặc 4 cầu thang xuống dưới. Một số cấp độ được đưa vào danh sách đen. Vì vậy, nếu quả bóng đến được đó, nó sẽ chết ngay lập tức. Chúng ta phải tìm số cách mà quả bóng có thể di chuyển xuống độ cao bằng 0. Nếu câu trả lời là quá lớn, hãy sửa kết quả bằng 10 ^ 9 + 7.

Vì vậy, nếu đầu vào giống như h =5 blacklist =[2, 1], thì đầu ra sẽ là 2, bởi vì ở vòng 0, di chuyển một bước trước (5 thành 4), sau đó trong vòng tiếp theo từ 4 đến 0. Một cách khác có thể là ở vòng 0, di chuyển hai bước (5 thành 3), sau đó ở vòng 3 tiếp theo là 0.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• danh sách đen:=một tập hợp mới từ các phần tử của danh sách cấm
• nếu 0 nằm trong danh sách đen hoặc h nằm trong danh sách đen, thì
  • trả về 0
• dp:=danh sách kích thước h và bên trong lưu trữ các cặp [0, 0] ở mỗi chỉ mục
• dp [0]:=[1, 1]
• m:=10 ^ 9 + 7
• đối với tôi trong phạm vi từ 1 đến h, hãy thực hiện
  • đối với mỗi x trong [1, 2, 3, 4], thực hiện
    • nếu i - x> =0 và i - x không nằm trong danh sách đen, thì
      • nếu x không giống 3, thì
        • dp [i, 0]:=dp [i, 0] + dp [i - x, 1]
      • nếu x không giống 2, thì
        • 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
• trả về dp [h, 0]

Ví dụ

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

 def giải quyết (h, danh sách đen):blacklist =set (danh sách đen) nếu 0 trong danh sách đen hoặc h trong danh sách đen:trả về 0 dp =[[0, 0] cho tôi trong phạm vi (h + 1)] dp [0] =[1, 1] m =10 ** 9 + 7 cho i trong khoảng (1, h + 1):cho x trong [1, 2, 3, 4]:nếu i - x> =0 và i - x không nằm trong danh sách đen: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 (giải (h, danh sách đen))  
 Đầu vào 
 
 5, [2, 1] 
 
 Đầu ra 
 
 2