Python/dynamic_programming/tribonacci.py at master · Scarfinos/Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Tribonacci sequence using Dynamic Programming


deftribonacci(num: int) ->list[int]:
"""
 Given a number, return first n Tribonacci Numbers.
 >>> tribonacci(5)
 [0, 0, 1, 1, 2]
 >>> tribonacci(8)
 [0, 0, 1, 1, 2, 4, 7, 13]
 """
dp= [0] *num
dp[2] =1

foriinrange(3, num):
dp[i] =dp[i-1] +dp[i-2] +dp[i-3]

returndp


if__name__=="__main__":
importdoctest

doctest.testmod()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Tribonacci sequence using Dynamic Programming


deftribonacci(num: int) ->list[int]:
"""
 Given a number, return first n Tribonacci Numbers.
 >>> tribonacci(5)
 [0, 0, 1, 1, 2]
 >>> tribonacci(8)
 [0, 0, 1, 1, 2, 4, 7, 13]
 """
dp= [0] *num
dp[2] =1

foriinrange(3, num):
dp[i] =dp[i-1] +dp[i-2] +dp[i-3]

returndp


if__name__=="__main__":
importdoctest

doctest.testmod()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Tribonacci sequence using Dynamic Programming


deftribonacci(num: int) ->list[int]:
"""
 Given a number, return first n Tribonacci Numbers.
 >>> tribonacci(5)
 [0, 0, 1, 1, 2]
 >>> tribonacci(8)
 [0, 0, 1, 1, 2, 4, 7, 13]
 """
dp= [0] *num
dp[2] =1

foriinrange(3, num):
dp[i] =dp[i-1] +dp[i-2] +dp[i-3]

returndp


if__name__=="__main__":
importdoctest

doctest.testmod()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Tribonacci sequence using Dynamic Programming


deftribonacci(num: int) ->list[int]:
"""
 Given a number, return first n Tribonacci Numbers.
 >>> tribonacci(5)
 [0, 0, 1, 1, 2]
 >>> tribonacci(8)
 [0, 0, 1, 1, 2, 4, 7, 13]
 """
dp= [0] *num
dp[2] =1

foriinrange(3, num):
dp[i] =dp[i-1] +dp[i-2] +dp[i-3]

returndp


if__name__=="__main__":
importdoctest

doctest.testmod()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Tribonacci sequence using Dynamic Programming


deftribonacci(num: int) ->list[int]:
"""
 Given a number, return first n Tribonacci Numbers.
 >>> tribonacci(5)
 [0, 0, 1, 1, 2]
 >>> tribonacci(8)
 [0, 0, 1, 1, 2, 4, 7, 13]
 """
dp= [0] *num
dp[2] =1

foriinrange(3, num):
dp[i] =dp[i-1] +dp[i-2] +dp[i-3]

returndp


if__name__=="__main__":
importdoctest

doctest.testmod()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Tribonacci sequence using Dynamic Programming


deftribonacci(num: int) ->list[int]:
"""
 Given a number, return first n Tribonacci Numbers.
 >>> tribonacci(5)
 [0, 0, 1, 1, 2]
 >>> tribonacci(8)
 [0, 0, 1, 1, 2, 4, 7, 13]
 """
dp= [0] *num
dp[2] =1

foriinrange(3, num):
dp[i] =dp[i-1] +dp[i-2] +dp[i-3]

returndp


if__name__=="__main__":
importdoctest

doctest.testmod()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Tribonacci sequence using Dynamic Programming


deftribonacci(num: int) ->list[int]:
"""
 Given a number, return first n Tribonacci Numbers.
 >>> tribonacci(5)
 [0, 0, 1, 1, 2]
 >>> tribonacci(8)
 [0, 0, 1, 1, 2, 4, 7, 13]
 """
dp= [0] *num
dp[2] =1

foriinrange(3, num):
dp[i] =dp[i-1] +dp[i-2] +dp[i-3]

returndp


if__name__=="__main__":
importdoctest

doctest.testmod()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Tribonacci sequence using Dynamic Programming


deftribonacci(num: int) ->list[int]:
"""
 Given a number, return first n Tribonacci Numbers.
 >>> tribonacci(5)
 [0, 0, 1, 1, 2]
 >>> tribonacci(8)
 [0, 0, 1, 1, 2, 4, 7, 13]
 """
dp= [0] *num
dp[2] =1

foriinrange(3, num):
dp[i] =dp[i-1] +dp[i-2] +dp[i-3]

returndp


if__name__=="__main__":
importdoctest

doctest.testmod()