I did not do anything but felt tired somehow.
I'm craving for yogurt.
Memoization and tabulation are both techniques used in dynamic programming.
Memoization is a top-down approach, whereas tabulation is a bottom-up approach.
Memoization solves a problem recursively and stores the results of subproblems, often in a hash table (dict in Python).
Tabulation solves a problem iteratively and fills up a table with the results of subproblems, often in a multi-dimensional array.
Calculating nth number of Fibonacci sequence is a very popular problem to demonstrate the power of dynamic programming.
In mathematics, the Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted Fn . The sequence commonly starts from 0 and 1, although some authors start the sequence from 1 and 1 or sometimes (as did Fibonacci) from 1 and 2. Starting from 0 and 1, the sequence begins.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ….
Here is the very simple implementation that returns the nth(0-index) number in Fibonacci sequence.
def fibonacci(n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)The problem with this approach is that the same results of subproblems are calculated multiple times. For example,
fibonacci(5)
= fibonacci(4) + fibonacci(3)
= (fibonacci(3) + fibonacci(2)) + fibonacci(3)In this example, fibonacci(3) will be calculated twice (fibonacci(2) will be calculated three times!). We can see that there are many redundant calculations happening.
Each node branches into two nodes. Numbers decrease by one for each round, meaning that the height of the tree is n. The number of nodes in the tree will be roughly 2 ** n, so the time complexity of the algorith, is O(2**n)
It's very obvious that we better store results of subproblems. For the previous example, storing the result of fibonacci(3) and refer to it next time it appears in the calculation will save time, removing redundant operations. (That's what you would do if you needed to do it manually with notes and pens, right?)
known = {}
def fibonacci(n: int) -> int:
# base conditions
if n == 0:
return 0
if n == 1:
return 1
if n in known:
return known[n]
nth = fibonacci(n - 1) + fibonacci(n - 2)
known[n] = nth # store the result of subproblems
return nthWith this approach, ith number of Fibonacci sequence won't be calculated twice. Instead, the value will be retrieved from the hash table.
It takes infinite() time to calculate 100th number of Fibonacci sequence with the previous approach with simple recursions, but with memoization, the program returns the result instantly.
The idea is that, to calcualte fibonacci(5), how about we calculate fibonacci(0), fibonacci(1), … fibonacci(4) first and store the results?
def fibonacci(n: int) -> int:
# ith element is the result of fibonacci(i)
# by filling up arr[0], arr[1], ..., we will get arr[n] in the end
arr: list[int] = [-1] * (n + 1)
# base conditions
arr[0] = 0
arr[1] = 1
for i in range(2, n + 1):
arr[i] = arr[i - 1] + arr[i - 2]
return arr[n]Actually, we don't need an array with length = n because we only need to track the previous element and the previous previous element.
Because each fibonacci(i) will be calculated only once, the time complexity of it is O(n), but unlike tabulation, checking the results of subproblems happens multiple times, and I can see that tabulation is always faster than memoization.
"""
max: p1 = p2 = p3 = 30
6 possible ways for each (p1, p2, p3) ** (90 total points // 2 points acquired for each round = 45)
~= 2 ** 45 * 3 ** 45 >> 2 ** 45 >> (2 ** 5) ** 9 = 1024 ** 9 > (10 ** 3) ** 9 = 10 ** 27 >> 10 * 9
Of course its verdict is Time limit exceeded!!!
Time limit exceeded on test 2
"""
def max_possible_draws(p1: int, p2: int, p3: int) -> int:
if (p1 + p2 + p3) % 2 == 1:
return -1
result = -1
def brute_force(p1: int, p2: int, p3: int, num_draws: int) -> None:
nonlocal result
if p1 < 0 or p2 < 0 or p3 < 0:
return
if p1 == 0 and p2 == 0 and p3 == 0:
result = max(result, num_draws) # how to access result??
# draw
brute_force(p1 - 1, p2 - 1, p3, num_draws + 1)
brute_force(p1, p2 - 1, p3 - 1, num_draws + 1)
brute_force(p1 - 1, p2, p3 - 1, num_draws + 1)
# someone win
brute_force(p1 - 2, p2, p3, num_draws)
brute_force(p1, p2 - 2, p3, num_draws)
brute_force(p1, p2, p3 - 2, num_draws)
brute_force(p1, p2, p3, 0)
return result
for _ in range(int(input())):
p1, p2, p3 = map(int, input().split())
print(max_possible_draws(p1, p2, p3))Of course, the brute force approach to check all possibilities doesn't work.
It's natural to think about memoization to store the results of subproblems.
memo = {} # {f"{p1},{p2},{p3}": num of max draws}
def max_possible_draws(p1: int, p2: int, p3: int) -> int:
key = f"{p1},{p2},{p3}"
if key in memo:
return memo[key]
# base
if p1 < 0 or p2 < 0 or p3 < 0:
memo[key] = -1
return -1
if p1 == 0 and p2 == 0 and p3 == 0:
memo[key] = 0
return 0
res = -1
# messy
tmp_res = max_possible_draws(p1 - 1, p2 - 1, p3)
if tmp_res != -1:
res = max(res, tmp_res + 1)
tmp_res = max_possible_draws(p1, p2 - 1, p3 - 1)
if tmp_res != -1:
res = max(res, tmp_res + 1)
tmp_res = max_possible_draws(p1 - 1, p2, p3 - 1)
if tmp_res != -1:
res = max(res, tmp_res + 1)
res = max(res, max_possible_draws(p1 - 2, p2, p3))
res = max(res, max_possible_draws(p1, p2 - 2, p3))
res = max(res, max_possible_draws(p1, p2, p3 - 2))
memo[key] = res
return res
for _ in range(int(input())):
p1, p2, p3 = map(int, input().split())
print(max_possible_draws(p1, p2, p3))I cannot implement the tabulation approach with 3-dimensional arrays to fill with my current ability. I'll consider that again in the future.
Hamburgers 1000 Spring rolls 1000
Total 2000 kcal
TODO: