.. role:: python(code)
   :language: python


.. index::
    memoization
    cache
    dynamic programming
    overlapping subproblems



..
    `Length of the longest common subsequence <ex:llcs>`_
    `Longest non-decreasing subsequence <ex:lnds>`_


.. _`sec:memoization`:

Dynamic Programming 
===================


Dynamic programming solves problems through smaller subproblems while storing
intermediate results.

It is especially useful when a problem has:

* **optimal substructure**: the optimal solution can be efficiently obtained from the optimal solution of its subproblems.
* **overlapping subproblems**: some subproblem solution are required in many other solution.


Memoization
-----------

**Caching** a costly tp obtain information means to store this information so that you can retrieve it cheaply later. 
**Memoization**  is a specific kind of caching: caching the results of function calls, 
usually to avoid recomputing the same subproblem. 
Memoization is one technique to dramatically speed up a calculation with overlapping subproblems. 
The trade-off is that the results are kept in memory. 


The recursive Fibonacci definition repeatedly requests identical values:

.. math::
    :label: eq:fibonacci

    \begin{cases}
    \mathcal{F}(n) = n & \textrm{if} ~ n \leq 1 \\
    \mathcal{F}(n) = \mathcal{F}(n-1) + \mathcal{F}(n-2) & \textrm{otherwise}
    \end{cases}

For example, computing a larger Fibonacci value may repeat 
several different recursive branches. 
Without memoization, identical computations are repeated. 
With memoization, every distinct Fibonacci state is computed once. 

.. figure:: fibonacci_dependencies.png
    :width: 200
    :alt: fibonacci_dependencies 

    Fibonacci dependencies up to F(6)

The previous figure represents the dependencies for a naive implementation of the Fibonacci sequence:

.. literalinclude:: ../../../../src/algo/memoization/memoization.py
    :pyobject: fibonacci_naive
    :name: fibonacci_naive
    :linenos:       
    :caption: src

The execution time are:

+-----+---------+
|   n |    t(s) |
+=====+=========+
|   0 | 4.9e-07 |
+-----+---------+
|   1 | 3.2e-07 |
+-----+---------+
|   2 | 5.1e-07 |
+-----+---------+
|   3 | 5.9e-07 |
+-----+---------+
|   4 | 4.7e-07 |
+-----+---------+
|   5 | 5.8e-07 |
+-----+---------+
|   6 | 8.2e-07 |
+-----+---------+
|   7 | 1.1e-06 |
+-----+---------+
|   8 | 1.5e-06 |
+-----+---------+
|   9 | 2.2e-06 |
+-----+---------+
|  10 | 3.5e-06 |
+-----+---------+
|  11 | 5.6e-06 |
+-----+---------+
|  12 | 8.9e-06 |
+-----+---------+
|  13 | 1.4e-05 |
+-----+---------+
|  14 | 2.3e-05 |
+-----+---------+
|  15 | 3.7e-05 |
+-----+---------+
|  16 | 6.1e-05 |
+-----+---------+
|  17 | 9.6e-05 |
+-----+---------+
|  18 | 1.6e-04 |
+-----+---------+
|  19 | 2.5e-04 |
+-----+---------+
|  20 | 4.1e-04 |
+-----+---------+
|  21 | 6.7e-04 |
+-----+---------+
|  22 | 1.1e-03 |
+-----+---------+
|  23 | 1.8e-03 |
+-----+---------+
|  24 | 2.9e-03 |
+-----+---------+
|  25 | 4.7e-03 |
+-----+---------+
|  26 | 7.4e-03 |
+-----+---------+
|  27 | 1.2e-02 |
+-----+---------+
|  28 | 2.0e-02 |
+-----+---------+
|  29 | 3.3e-02 |
+-----+---------+
|  30 | 5.3e-02 |
+-----+---------+
|  31 | 8.5e-02 |
+-----+---------+
|  32 | 1.4e-01 |
+-----+---------+
|  33 | 2.2e-01 |
+-----+---------+
|  34 | 3.6e-01 |
+-----+---------+
|  35 | 5.8e-01 |
+-----+---------+
|  36 | 9.5e-01 |
+-----+---------+
|  37 | 1.5e+00 |
+-----+---------+
|  38 | 2.5e+00 |
+-----+---------+
|  39 | 4.1e+00 |
+-----+---------+
|  40 | 6.6e+00 |
+-----+---------+
|  41 | 1.1e+01 |
+-----+---------+
|  42 | 1.7e+01 |
+-----+---------+

Execution times rapidly become unacceptable for such a simple problem. 
The number of subproblems increases exponentially, so is the execution time. 
A solution has been presented in the :python:`functools` :ref:`section <sec:functools>` 
with the :python:`cache` decorator:


.. literalinclude:: ../../../../src/algo/memoization/memoization.py
    :pyobject: fibonacci
    :name: fibonacci
    :linenos:       
    :caption: src

+-----+---------+
|   n |    t(s) |
+=====+=========+
|   0 | 7.6e-07 |
+-----+---------+
|   1 | 5.5e-07 |
+-----+---------+
|   2 | 7.5e-07 |
+-----+---------+
|   3 | 7.0e-07 |
+-----+---------+
|   4 | 4.9e-07 |
+-----+---------+
|   5 | 4.7e-07 |
+-----+---------+
|   6 | 3.7e-07 |
+-----+---------+
|   7 | 3.5e-07 |
+-----+---------+
|   8 | 3.6e-07 |
+-----+---------+
|   9 | 3.2e-07 |
+-----+---------+
|  10 | 4.1e-07 |
+-----+---------+
|  11 | 3.5e-07 |
+-----+---------+
|  12 | 3.2e-07 |
+-----+---------+
|  13 | 3.1e-07 |
+-----+---------+
|  14 | 4.1e-07 |
+-----+---------+
|  15 | 4.3e-07 |
+-----+---------+
|  16 | 3.7e-07 |
+-----+---------+
|  17 | 3.4e-07 |
+-----+---------+
|  18 | 2.9e-07 |
+-----+---------+
|  19 | 3.2e-07 |
+-----+---------+
|  20 | 3.0e-07 |
+-----+---------+
|  21 | 6.3e-07 |
+-----+---------+
|  22 | 3.2e-07 |
+-----+---------+
|  23 | 3.3e-07 |
+-----+---------+
|  24 | 3.2e-07 |
+-----+---------+
|  25 | 3.4e-07 |
+-----+---------+
|  26 | 3.4e-07 |
+-----+---------+
|  27 | 3.2e-07 |
+-----+---------+
|  28 | 3.1e-07 |
+-----+---------+
|  29 | 3.2e-07 |
+-----+---------+
|  30 | 3.4e-07 |
+-----+---------+
|  31 | 3.4e-07 |
+-----+---------+
|  32 | 3.1e-07 |
+-----+---------+
|  33 | 3.4e-07 |
+-----+---------+
|  34 | 3.1e-07 |
+-----+---------+
|  35 | 3.1e-07 |
+-----+---------+
|  36 | 3.5e-07 |
+-----+---------+
|  37 | 3.3e-07 |
+-----+---------+
|  38 | 3.0e-07 |
+-----+---------+
|  39 | 2.9e-07 |
+-----+---------+
|  40 | 3.0e-07 |
+-----+---------+
|  41 | 3.0e-07 |
+-----+---------+
|  42 | 7.5e-07 |
+-----+---------+


Subproblem definition
---------------------

Usually, the hard part lies in the subproblem definition. 
They can (and even must) overlap; they must form an optimal substructure; the number of input parameters 
must be minimal. 


.. admonition:: Exercise (intermediate)

    The length of the longest common subsequence is a typical dynamic programming exercise. 
    The goal is to find inside two strings, the length of the longest subsequence of 
    potentially non adjacent common letters. 
    Imagine that you want to quantify how similar two mutated DNA are.

    
    1. Express the subproblem, implement. The hints below will probably be needed.
    2. Understand and comment the code in the collapsable section below.
    3. Test.
    4. Complexity, with or without memoization.

.. _`ex:llcs`:

.. collapse:: Hint 1
 
    .. literalinclude:: ../../../../src/algo/memoization/memoization.py
        :pyobject: length_longest_common_sequence_empty_0
        :name: length_longest_common_sequence_empty_0
        :linenos:       
        :caption: src   


.. collapse:: Hint 2

    The internal structure is given below. 
    
    .. literalinclude:: ../../../../src/algo/memoization/memoization.py
        :pyobject: length_longest_common_sequence_empty_1
        :name: length_longest_common_sequence_empty_1
        :linenos:       
        :caption: src   

.. collapse:: Correction of 1.
      

    .. literalinclude:: ../../../../src/algo/memoization/memoization.py
        :pyobject: length_longest_common_sequence_uncommented
        :name: length_longest_common_sequence_uncommented
        :linenos:       
        :caption: src   



.. collapse:: Correction
   
    2.

    .. literalinclude:: ../../../../src/algo/memoization/memoization.py
        :pyobject: length_longest_common_sequence
        :name: length_longest_common_sequence
        :linenos:       
        :caption: src 

    3.

    .. literalinclude:: ../../../../tests/algo/memoization/test_memoization.py
        :pyobject: test_length_longest_common_sequence
        :name: test_length_longest_common_sequence
        :linenos:       
        :caption: tests   

    4.

        For the complexity, let us focus on the case without any common elements. 
        It means that at every recursion, two recursions are called 
        (one dropping the last element of the first sequence, the other dropping the last element of the second). 
        Each call makes one comparison which is defined as the costly operation. 

        It means that a tree is created, with a branching factor of 2 is created. 
        If one starts with two sequences of length :math:`n`, the path where one drops systematically the last element of the first sequence 
        has a depth of :math:`n`. 
        The path where one drops alternatively from the first and the second sequence has a depth of :math:`2 n`.
        At each depth level, the total number of calls is doubled. 
        The growth is exponential: :math:`2^{2n}`.

        Now, with memoization, the problem can be looked from an other perspective. 
        The caching is performed on 2 integers: the current index of the first sequence, and the one of the second. 
        It means that the cache contains at most :math:`n^2` entries, and as a result the function has been executed at most :math:`n^2` times.
          

.. note:: 

    The function :python:`max` (and :python:`min` and :python:`sort`) has a very useful optional argument: :python:`key=`. 
    This argument is a callable which used on the element prior to comparison.

    For example :python:`max([-3, 2])` is :python:`2`,

    but :python:`max([-3, 2], key=abs)` is :python:`-3`

    It means that one can concisely select the longest sequence between several:

    :python:`max([(2, 2), (4, 4, 4, 4), (3, 3, 3)], key=len)` is :python:`(4, 4, 4, 4)`

.. admonition:: Exercise (difficult)

    The longest non-decreasing subsequence is a classic dynamic programming problem. 
    The goal is to find a sequence of potentially non adjacent element. 
    The subsequence consists of increasing (or equal) elements inside another sequence. 
    For example: in :python:`[3, 1, 4, 2, 1, 2 , 3]`, :python:`[1, 4]` and :python:`[2, 2 , 3]` 
    are non-decreasing subsequences, however the longest is :python:`[1, 2, 2 , 3]`. 
    
    1. Express the subproblem, implement. The hints below will probably be needed.
    2. Understand and comment the code in the collapsable section below.
    3. Test.

.. collapse:: Hint 1

    The hardest part of the exercise is to find what the subproblem is:

    .. literalinclude:: ../../../../src/algo/memoization/memoization.py
        :pyobject: longest_nondecreasing_subsequence_empty_0
        :name: longest_nondecreasing_subsequence_empty_0
        :linenos:       
        :caption: src    

.. collapse:: Hint 2

    The internal structure is given below, the lines with :python:`...` or ended by :python:`#` 
    have to be completed:

    .. literalinclude:: ../../../../src/algo/memoization/memoization.py
        :pyobject: longest_nondecreasing_subsequence_empty_1
        :name: longest_nondecreasing_subsequence_empty_1
        :linenos:       
        :caption: src       

.. _`ex:lnds`:

.. collapse:: Correction of 1.

    1.

    .. literalinclude:: ../../../../src/algo/memoization/memoization.py
        :pyobject: longest_nondecreasing_subsequence_uncommented
        :name: longest_nondecreasing_subsequence_uncommented
        :linenos:       
        :caption: src    

.. collapse:: Correction

    2.

    .. literalinclude:: ../../../../src/algo/memoization/memoization.py
        :pyobject: longest_nondecreasing_subsequence
        :name: longest_nondecreasing_subsequence
        :linenos:       
        :caption: src    

    3.

    .. literalinclude:: ../../../../tests/algo/memoization/test_memoization.py
        :pyobject: test_longest_nondecreasing_subsequence
        :name: test_longest_nondecreasing_subsequence
        :linenos:       
        :caption: tests