N-th Tribonacci Number
Statement
Given a number n, calculate the corresponding Tribonacci number. The Tribonacci sequence is defined below.
Constraints
- 0 ≤
n≤ 37
Solution
"""
production algorithm
"""
class Solution:
def tribonacci(self, n):
"""
time complexity O(n)
space complexity O(1)
"""
if n == 0:
return 0
if n == 1 or n == 2:
return 1
ta, tb, tc = 0, 1, 1
for _ in range(3, n + 1):
ta, tb, tc = tb, tc, ta + tb + tc
return tc"""
unit tests
"""
from unittest import TestCase
from algorithms.dynamic_programming.nth_tribonacci_number.solution import Solution
class SolutionTestCase(TestCase):
def test_n_is_base_case_zero(self):
# Given
n = 0
solution = Solution()
# When
actual = solution.tribonacci(n)
# Then
expected = 0
self.assertEqual(actual, expected)
def test_n_is_base_case_one(self):
# Given
n = 1
solution = Solution()
# When
actual = solution.tribonacci(n)
# Then
expected = 1
self.assertEqual(actual, expected)
def test_n_is_base_case_two(self):
# Given
n = 2
solution = Solution()
# When
actual = solution.tribonacci(n)
# Then
expected = 1
self.assertEqual(actual, expected)
def test_n_is_not_base_case(self):
# Given
n = 10
solution = Solution()
# When
actual = solution.tribonacci(n)
# Then
expected = 149
self.assertEqual(actual, expected)Strategy
Dynamic Programming.
Explanation
Beyond the base cases which are trivial, there are three pieces of information used to calculate the nth Tribonacci number. ta, tb, and tc hold the value of the current n-3th, n-2th, and n-1th Tribonacci number respectively. An iteration occurs, where ta, tb, and tc are incremented to the next values of the Tribonacci sequence. The iteration ends when the nth Tribonacci number is calculated.
Notice, that the problem has optimal substructure, i.e. the optimal solution of a larger Tribonacci number can be found from the optimal solution of a smaller Tribonnaci number. Also notice, that the problem has overlapping subproblems, i.e. the optimal solution of a smaller Tribonacci number can be reused to find the optimal solution of distinct larger Tribonacci numbers. Since the problem has optimal substructure and overlapping subproblems, then dynamic programming can be used to solve the problem.
Time Complexity
At worst, the algorithm iterates a number proportional to n number of times. Therefore, the time complexity of the algorithm is O(n).
Space Complexity
The auxiliary space complexity of the algorithm is O(1).
