Part $2-$ Rolling Dice to a Total

Given an n$-$sided die, we want to determine how many different ways one could repeatedly sum die rolls and get to a given total.

For instance, given a $4-$sided die, we could obtain a total of $3$ in four different ways:

$1+1+1($rolling a $1$ three times$)$

$1+2($rolling a $1$ and then rolling a $2)$

$2+1($rolling a $2$ and then rolling a $1)$

$3($rolling a $3)$

We will write two different functions to solve this problem. Each functions takes $n($the number of sides on the die$)$ and total $($the total to which we'll sum rolls$)$ as input. Each function must use its corresponding dynamic programming methodology in order to solve the problem.

ways$\_$to$\_$sum$\_$memo$($n$,$ total$)$

must use memoization

vays$\_$to$\_$sum$\_$tab$($n$,$ total$)$

must use tabulation

$$ ways$\_$to$\_$sum$\_$memo $,$ total $=3)$

$4$

$$ ways$\_$to$\_$sum$\_$tab$(n=4,$ total$=3)$

$4$

Imports

No imports allowed on this assignment, with the following exceptions:

Any modules you have written yourself

typing $-$ this is not required, but some students have requested it

For testing only $($do not use these for functionality in any other classes$/$algorithms$)$:

unittest

random

Submission Requirements

Students must submit individually by the due date.

At a minimum, you must submit the following files:

linked$\_1$ist.py

vays$\_$to$\_$sum.py

Additionally, you must include any other files necessary for your code to run, such as modules containing data structures you wrote yourself.

Note that we are not requiring tests here. We have instead provided tests for you. We'll begin requiring tests again for the next homework, but we are prioritizing giving you multiple chances to practice recursion this week, since it's an area where we typically need a lot of practice. See here for some more practice problems.