To solve this problem, we need to compute the nth term of a sequence where each term is the sum of the two preceding terms. This sequence is commonly associated with problems like tiling a 2xn grid with dominoes or climbing stairs with 1 or 2 steps.
Approach
The sequence follows these rules:
- The first term (n=1) is 1.
- The second term (n=2) is 2.
- For any term n > 2, the term is the sum of the (n-1)th and (n-2)th terms (i.e., f(n) = f(n-1) + f(n-2)).
We use an iterative approach to compute the sequence efficiently, avoiding recursion depth issues and ensuring optimal performance even for larger values of n.
Solution Code
def compute_sequence(n):
if n == 1:
return 1
a, b = 1, 2
for _ in range(3, n + 1):
c = a + b
a = b
b = c
return b
# Example usage:
# print(compute_sequence(5)) # Output: 8
# print(compute_sequence(6)) # Output: 13
Explanation
- Base Cases: Directly return 1 for n=1 and 2 for n=2.
- Iterative Calculation: For n > 2, we start with the first two terms and iteratively compute each subsequent term by summing the previous two terms. This approach runs in O(n) time complexity and O(1) space complexity, making it efficient for large values of n.
This solution is optimal and handles all valid values of n (positive integers) correctly. If modulo operations are required (e.g., for very large numbers), you can add % MOD (where MOD is the desired modulus, like 10^9+7) to the sum operation. For example: c = (a + b) % MOD.
Let me know if you need to adjust the solution for specific constraints!


作者声明:本文包含人工智能生成内容。