this is for holding javascript data
Niclas Alexandersson edited dynamic.tex
almost 10 years ago
Commit id: e12e67b6301309671d1d7ebea4e482c00eb9b505
deletions | additions
diff --git a/dynamic.tex b/dynamic.tex
index 8751a00..8f2491f 100644
--- a/dynamic.tex
+++ b/dynamic.tex
...
\subsection{Dynamic programming}
With the above algorithm, consider the following paths of execution:
\begin{verbatim}
mr(i, x, 0)
mr(i, x-1, 1)
...
mr(i-1, x-1, 0)
...
mr(i-2, x-1, 0)
mr(i-1, x, 0)
...
mr(i-1, x-1, 1)
...
mr(i-2, x-1, 0)
\end{verbatim}
Looking at this tree, we can see that \verb|mr(i-2, x-1, 0)| is computed twice. The same will be true for many other values in the execution tree. Thus, it is likely that dynamic programming will be of use here.
Using dynamic programming, we Another thing to realise, is that \verb|mr(i, x, a)| where $a>0$ can only be called from \verb|mr(i, x+1, a-1)|, \verb|mr(i, x, 0)| can
improve be called from \verb|mr(i+1, x, a)| with any value of $a$. Since each unique \verb|mr(i, x, a)| is only computed once, it therefore becomes wasteful to store anything other than values where $a=0$ in memory. To avoid having to treat $a=0$ and $a>0$ as separate cases, we change the
time complexity a lot: algorithm to use loops instead of recursive calls to \verb|mr(i, x-1, a+1)|, and then add memory to it.
\begin{verbatim}