Giả sử chúng ta đang ở vị trí 0 của n độ dài danh sách, và trên mỗi bước, chúng ta có thể di chuyển sang phải một nơi hoặc sang trái một nơi (không vượt quá giới hạn), hoặc giữ nguyên vị trí. Bây giờ nếu chúng ta có thể thực hiện chính xác k bước, thì chúng ta phải tìm xem chúng ta có thể đi bao nhiêu bước duy nhất và quay trở lại chỉ số 0. Nếu câu trả lời là rất lớn, hãy trả về nó mod 10 ^ 9 + 7.
Vì vậy, nếu đầu vào là n =7 k =4, thì đầu ra sẽ là 9, như các hành động-
- [Phải, Phải, Trái, Trái],
- [Phải, Trái, Phải, Trái],
- [Ở lại, Ở lại, Ở lại, Ở lại],
- [Phải, Trái, Ở lại, Ở lại],
- [Ở lại, Ở lại, Phải, Trái],
- [Phải, Ở lại, Ở lại, Bên trái],
- [Phải, Ở lại, Bên trái, Ở lại],
- [Ở lại, Phải, Trái, Ở lại],
- [Ở lại, Bên phải, Ở lại, Bên trái],
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- m:=10 ^ 9 + 7
- N:=chiều dài
- Định nghĩa một hàm dp (). Điều này sẽ khiến tôi mất hứng thú
- nếu các bước nhảy giống 0, thì
- return (true khi tôi giống 0, nếu không, false)
- count:=dp (i, jumps - 1)
- nếu tôi> =0, thì
- count:=count + dp (i + 1, jumps - 1)
- nếu tôi <=N - 1, thì
- count:=count + dp (i - 1, jumps - 1)
- số lượng trả lại
- Từ phương thức chính, hãy làm như sau:
- return dp (0, n) mod m
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution: def solve(self, length, n): MOD = 10 ** 9 + 7 N = length def dp(i, jumps): if jumps == 0: return +(i == 0) count = dp(i, jumps - 1) if i >= 0: count += dp(i + 1, jumps - 1) if i <= N - 1: count += dp(i - 1, jumps - 1) return count return dp(0, n) % MOD ob = Solution() n = 7 k = 4 print(ob.solve(n, k))
Đầu vào
7, 4
Đầu ra
9