#!/usr/bin/env python
# coding: utf-8

# # Memoization Exercises
# 
# 

# ## 1. Fibonnacci Sequence
# 
# The fibonnacci sequence is defined as below :
# 
# $$
# \Large
# f_n = \begin{cases}n \text{ if } n \leq 1\\
#     f_{n-1} + f_{n-2} \text{ if } n > 1
#     \end{cases}
# $$
# 
# ### 1.1 
# Write a recursive function `fib(n)` that takes an integer `n` and returns $f_n$.

# In[64]:





# ### 1.2 
# Add `print("Calculating fib of " + str(n))` at the beginning of your function, and run the cell below :

# In[ ]:


fib(7)


# How many times does it calculate fib of `1` ?

# In[11]:


# Answer here


# ## 2. Fibonacci Sequence - Memoized

# 
# We are going to store things we have computed before in a list `mem` such that <br/><br/>
# $$
# mem[i] = \begin{cases}-1 \text{ if we haven't computed fib(i) before }\\
#       f_i \text{ if we have already computed it}
#     \end{cases}
# $$
# 
# ### 2.1
# Write a function `create_memory(n)` that takes an integer `n` and returns a list L of length `n` that contains the integer `-1` repeated `n` times.
# 
# 

# In[ ]:





# 
# ### 2.2
# Write a function `check(i, mem)` that takes an index `i` and a list `mem` and returns `True` if `mem[i]` is not equal to `-1`:

# In[17]:





# ### 2.3
# Write a function `add(mem, i, value)` that takes a list `mem`, an index `i` and an integer `value` and that stores the integer `value` in the list `mem` at index `i` :

# In[ ]:





# ### 2.4
# Write a recursive function `memo_fib(n, mem)` that takes an integer `n` and a list `mem` and returns $f_n$. <br/>
# Here is how it should work : <br/>
# <ul>
#     <li> If `mem[n]` is **not** equal to `-1`, it should return `mem[n]`</li>
#     <li> If `mem[n]` is equal to `-1`, it should compute $f_n$ recursively and store it in `mem[n]` before returning it.</li>
# </ul>

# In[ ]:





# ### 2.5
# Write a function `fib(n)` that takes an integer `n` and returns $f_n$. It should use `create_memory(n)` and `memo_fib(n, mem)`:

# In[ ]:





# ## 3. Making Basketball Teams
# 
# You have `n` classmates. You want to create a team of `k` players. How many different teams can you create ?
# 
# You may have seen in math class that the number we are looking for is :
# $$
# \Large
# \binom{n}{k}
# $$
# 
# To choose your team, you can either pick the tallest classmate and then pick the remaining `k-1` players, or you can decide to leave out your tallest classmate and pick a team among `n-1` classmates. 
# 
# This yields the recursive formula :
# $$
# \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}
# $$
# 
# 
# ### 3.1
# Write a recursive function `binom(n, k)` that takes two integers `n` and `k` and returns $\binom{n}{k}$ :
# 
# *Hint : Think of your base case carefully. What is $\binom{n}{0}$ ? What is $\binom{0}{k}$ if $k \neq 0$ ?*
# 

# In[53]:





# ### 3.2
# We're going to create a list of lists called `mem` such that : <br/><br/>
# $$
# mem[i][j] =
# \begin{cases}
# -1 \text{  if }\binom{i}{j} \text{ has not been computed before}\\
# \binom{i}{j} \text{ if it has}
# \end{cases}
# $$
# 
# The code below generates a list of lists `lst` with 3 rows and 4 columns that contains `-1`s:
# ```[python]
# lst = [ [-1] * 4 ] * 3
# ```
# 
# Write a function `create_memory(r, c)` that takes two integers `r` and `c` and returns a list of lists with `r` rows and `c` colums.

# In[ ]:





# ### 3.3
# Write a function `memo_binom(n, k, mem)` that takes two integers `n`, `k` and a list of lists `mem` and that returns $\binom{n}{k}$. 

# In[54]:





# ### 3.4
# Write a function `binom(n, k)` that returns $\binom{n}{k}$. It should use `create_memory(r, c)` and `memo_binom(n, k, mem)`.

# In[ ]:





# ## 4. Moving in a grid
# 
# 
# We want to find the number of paths that go from `A` to `Z` in the grid below :
# 
# <center>
#     <img src = "gridpaths.png" width = "500px">
# </center>
# 
# Two examples paths are drawn below in red: 
# 
# <table>
#     <tr>
#     <td>
#         <img src = "onepath.png" width = "300px"> </td>
#         <td><img src = "path2.png" width = "300px"> </td>
#     
#     </tr>
# </table>
# 
# We number the points in the grid like so :
#  <img src = "numbered.png" width = "300px"> 
# 
# Let $T(a,b)$ denote the number of ways of getting from (0,0) to (a, b). For example $T(0,1) = 1$ and $T(1,1) = 3$
# 
# ##### Recursive formula :
# 
# If you know $T(a-1, b)$, $T(a, b-1)$ and $T(a-1, b-1)$, how can you find $T(a,b)$ ? 
# 
# ### 4.1
# Write a recursive function `T(a,b)` that takes two integers `a` and `b` and returns the number of ways of getting from (0,0) to (a,b):
# 

# In[61]:





# ### 4.2
# How many ways are there of getting from `A` to `Z` ?
# <br/>
# 
# 

# In[12]:


# Answer here



# ### 4.3
# Following the previous exercise's procedure, write a function `memo_T(a,b)` that takes integers `a` and `b` and returns $T(a,b)$: 

# In[ ]:





# ### 4.4 
# Write a function `T(a, b)` that takes two integers `a` and `b` and returns the number of ways of getting from (0,0) to (a,b). It should use `memo_T(a, b)` :

# In[ ]:





# # Optional Exercises
# 

# ## 5. Min Number of Ways to Make Change
# 
# You saw in lecture how to get the number of ways to make change using recursion and memoization. Now, we are going to change the question a bit, and get minimum number of ways to make change. 
# 
# Suppose you live in a country whose coin denominations are in the list ```L```. For example, in Ethiopia we would have ```L = [1,5,10,25,50,100]```, but other countries have different coin systems. Implement a function ```makeChange(n, L)``` which returns the minimum number of coins needed to make change for ```n``` cents using the coins in ```L```. 
# 
# For example, ```makeChange(14, [1,5,10,25,50,100])``` should return ```5```, since you can make change for ```14``` cents by giving one ```10```-cent piece and four ```1```-cent pieces, for a total of ```5``` coins (you could also give two ```5```-cent pieces and four ```1```-cent pieces, or ```14``` ```1```-cent pieces, but those options would each require more coins). If it is impossible to make change for ```n``` cents using ```L```, you should return ```-1```. For example, ```makeChange(3, [2, 5])``` should return ```-1``` since there is no way to make change for ```3``` cents using ```2```-cent and ```5```-cent pieces.
# 
# ### 5.1 
# First implement ```makeChange``` using plain recursion.

# In[ ]:





# ### 5.2
# Implement a faster version of `makeChange` using memoization.

# In[ ]:





# ## 6. Longest Increasing Subsequence 
# 
# Write a function ```lis(L)``` which takes as input a list of integers ```L``` and outputs the length of the longest increasing subsequence (lis) of ```L```. A subsequence of ```L``` is a sublist of ```L``` that does not have to be contiguous. For example, ```[1,5,9]``` is a subsequence of the list ```L = [1,2,3,4,5,6,7,8,9]``` since ```1,5,9``` appear in the list ```L``` in the same order (though just not in a row). ```9,5,1``` is not a subsequence of ```L``` since it does not appear in ```L``` in that order.
# 
# ### 6.1
# First implement ```lis``` using plain recursion.

# In[5]:





# ## 6.2 
# Implement a faster version of `lis` using memoization.

# In[ ]:





# ## 7. Longest Common Subsequence 
# 
# Write the function `lcs(s1, s2)` which takes as an input two strings and outputs the length of the longest common substring between the two. A subsequence of string```s``` is a set of letters that does not have to be contiguous. For example, the longest common subsequence of `'apple'` and `'pimple'`  is `'pple'`, so the function would return `4`. 

#