Davis có một số cầu thang trong nhà và cậu thích leo mỗi lần 1, 2 hoặc 3 bậc. Davis muốn biết có bao nhiêu cách khác nhau để đi lên đến đỉnh cầu thang.
Cho chiều cao của từng cầu thang trong số s cầu thang trong nhà, hãy tìm và in ra số cách Davis có thể leo mỗi cầu thang, lấy phần dư cho 10^10 + 7, mỗi kết quả trên một dòng.
Với n = 5.
Cầu thang có 5 bậc. Davis có thể bước theo các cách sau:
1 1 1 1 1
1 1 1 2
1 1 2 1
1 2 1 1
2 1 1 1
1 2 2
2 2 1
2 1 2
1 1 3
1 3 1
3 1 1
2 3
3 2
Có 13 cách để Davis đi hết 5 bậc và:
13 modulo 10000000007 = 13
Hoàn thành hàm stepPerms bằng cách sử dụng đệ quy.
Hàm stepPerms có tham số:
Bạn đang leo một cầu thang. Cần n bậc để lên đến đỉnh.
Mỗi lần bạn có thể leo 1 hoặc 2 bậc. Hỏi có bao nhiêu cách khác nhau để bạn có thể leo đến đỉnh?
| Input | Output | Giải thích |
|---|---|---|
| n = 2 | 2 | Có hai cách để lên đến đỉnh: 1. 1 bậc + 1 bậc 2. 2 bậc |
| n = 3 | 3 | Có ba cách để lên đến đỉnh: 1. 1 bậc + 1 bậc + 1 bậc 2. 1 bậc + 2 bậc 3. 2 bậc + 1 bậc |
Cho một mảng số nguyên cost, trong đó cost[i] là chi phí của bậc thứ i trên cầu thang.
Sau khi trả chi phí của một bậc, bạn có thể leo lên 1 hoặc 2 bậc.
Bạn có thể bắt đầu từ bậc có chỉ số 0 hoặc bậc có chỉ số 1.
Hãy trả về chi phí nhỏ nhất để lên đến đỉnh cầu thang.
| Input | Output | Giải thích |
|---|---|---|
| cost = [10,15,20] | 15 | Bắt đầu tại chỉ số 1. Trả 15 và leo 2 bậc để đến đỉnh. Tổng chi phí là 15. |
| cost = [1,100,1,1,1,100,1,1,100,1] | 6 | Bắt đầu tại chỉ số 0. Trả 1 và leo 2 bậc đến chỉ số 2. Trả 1 và leo 2 bậc đến chỉ số 4. Trả 1 và leo 2 bậc đến chỉ số 6. Trả 1 và leo 1 bậc đến chỉ số 7. Trả 1 và leo 2 bậc đến chỉ số 9. Trả 1 và leo 1 bậc để đến đỉnh. Tổng chi phí là 6. |
Bạn là một tên trộm chuyên nghiệp đang lên kế hoạch trộm tiền từ các ngôi nhà dọc theo một con phố.
Mỗi ngôi nhà có một số tiền nhất định. Ràng buộc duy nhất khiến bạn không thể trộm tất cả các ngôi nhà là các ngôi nhà liền kề có hệ thống an ninh kết nối với nhau và hệ thống sẽ tự động báo cảnh sát nếu hai ngôi nhà liền kề bị đột nhập trong cùng một đêm.
Cho một mảng số nguyên nums biểu diễn số tiền trong mỗi ngôi nhà, hãy trả về số tiền lớn nhất có thể lấy được trong đêm mà không làm hệ thống báo cảnh sát.
| Input | Output | Giải thích |
|---|---|---|
| nums = [1,2,3,1] | 4 | Trộm nhà 1 (1) và sau đó trộm nhà 3 (3). Tổng số tiền = 1 + 3 = 4. |
| nums = [2,7,9,3,1] | 12 | Trộm nhà 1 (2), nhà 3 (9) và nhà 5 (1). Tổng số tiền = 2 + 9 + 1 = 12. |
Cho một mảng triangle, hãy trả về tổng đường đi nhỏ nhất từ đỉnh xuống đáy.
Ở mỗi bước, bạn có thể đi đến một số liền kề ở hàng bên dưới.
Cụ thể hơn, nếu đang ở chỉ số i của hàng hiện tại, bạn có thể di chuyển đến chỉ số i hoặc i + 1 ở hàng tiếp theo.
| Input | Output | Giải thích |
|---|---|---|
| triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] | 11 | Tam giác: 2 3 4 6 5 7 4 1 8 3 Tổng đường đi nhỏ nhất từ trên xuống dưới là 2 + 3 + 5 + 1 = 11. |
| triangle = [[-10]] | -10 |
Bạn đã chặn được một thông điệp bí mật được mã hóa dưới dạng một chuỗi các chữ số. Thông điệp được giải mã theo quy tắc:
"1" → 'A'
"2" → 'B'
...
"25" → 'Y'
"26" → 'Z'
Tuy nhiên, khi giải mã thông điệp, bạn nhận ra rằng có nhiều cách khác nhau để giải mã vì một số mã có thể nằm trong các mã khác, chẳng hạn "2" và "5" trong "25".
Ví dụ, "11106" có thể được giải mã thành:
Lưu ý: Có thể tồn tại những chuỗi không thể giải mã.
Cho một chuỗi s chỉ chứa các chữ số, hãy trả về số cách giải mã chuỗi đó. Nếu toàn bộ chuỗi không thể được giải mã theo bất kỳ cách hợp lệ nào, trả về 0.
Các bộ test được tạo sao cho đáp án nằm trong phạm vi số nguyên 32-bit.
| Input | Output | Giải thích |
|---|---|---|
| s = "12" | 2 | "12" có thể được giải mã thành "AB" (1 2) hoặc "L" (12). |