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

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

must use tabulation

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

$4$

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

$4$

FIX THE TABULATION CODE SO IT RETURNS THE CORRECT VALUES. $($FEEL FREE TO CHANGE ANYTHING ABOUT THE CODE FOR IT TO WORK, JUST MAKE SURE THE CODE USES TABULATION$)$

$($MY CURRENT CODE$)$:

def ways$\_$to$\_$sum$\_$tab$($n$,$ total$)$:

$"""$Uses tabulation to determine the number of ways to get the given total with an n$-$sided die"""

# Initialize a table to store subproblem solutions

table $=[0]*($total $+1)$

table$[0]=1$

# Fill in the table using previously computed solutions

for i in range$(1,$ n $+1)$:

for j in range$($i$,$ total $+1)$:

table$[$j$]+=$ table$[$j $-$ i$]$

return table$[$total$]$

$($TEST CASES FOR THE CODE AND THE EXPECTED RETURNED VALUES FOR EACH TEST$)$

if $\_\_$name$\_\_==\text{'}\_\_$main$\_\_\text{'}$:

print$($ways$\_$to$\_$sum$\_$tab$(4,3))$ # Expected value $=4$

print$($ways$\_$to$\_$sum$\_$tab$(4,9))$ # Expected value $=108$

print$($ways$\_$to$\_$sum$\_$tab$(4,12))$ # Expected value $=1490$

print$($ways$\_$to$\_$sum$\_$tab$(6,3))$ # Expected value $=4$

print$($ways$\_$to$\_$sum$\_$tab$(6,9))$ # Expected value $=248$

print$($ways$\_$to$\_$sum$\_$tab$(6,12))$ # Expected value $=1936$

print$($ways$\_$to$\_$sum$\_$tab$(20,3))$ # Expected value $=4$

print$($ways$\_$to$\_$sum$\_$tab$(20,9))$ # Expected value $=256$

print$($ways$\_$to$\_$sum$\_$tab$(20,12))$ # Expected value $=2048$

print$($ways$\_$to$\_$sum$\_$tab$(20,20))$ # Expected value $=524288$

print$($ways$\_$to$\_$sum$\_$tab$(20,29))$ # Expected value $=268434176$

$($THE CODES CURRENT VALUES RETURNED FOR THE TESTS$)$:

$3$

$18$

$34$

$3$

$26$

$58$

$3$

$30$

$77$

$627$

$4498$