How to Count Dice Rolls - An Introduction to Dynamic Programming

Dynamic programming is a common technique in computer science for solving problems more efficiently. Here, we introduce the ideas and motivations for dynamic programming by counting the number of ways to roll dice.

0:00 Counting Dice
1:21 Brute-Force Methods
2:32 Recursive Problem Solving
5:53 Lookup Tables

***

[chaotech]

Since you are computing an iterated convolution, you could also use a fourier transform to directly compute the result, eliminating the need for dynamic programming. With a bit of optimization you can get to a space complexity of n and a time complexity of nlogn. It's an interesting use of the DFT considering most YouTube content only uses it for polynomial multiplication.

[pafnutiytheartist]

I love how your lookup table is a literal table

[BigFatSandwitch]

I came here after watching your videos on edx - web development in js and python. So far I have been loving the lectures

[adamaranyi]

For the past 9~ hours I have been trying to figure out the pattern only by analyzing a few example results i already had. You have provided a clear and understandable explanation for the connection between these seemingly random numbers in the table. Thank you very much!

[marshallc]

I found Eratosthenes' Sieve to be a much more intuitive implementation of this idea ("bottom-up" instead of "top-down".) To know if N is prime or composite, make an array of N elements and mark every element as prime. Starting at 2 and ending at sqrt(N), mark every multiple of 2 as composite. Then mark every multiple of 3 as composite. Then because 4 is already marked composite, skip to 5, etc. When we get to sqrt(N) then we know that either N is composite because we marked it composite when we were on its divisor M or we never marked it as a multiple of any integer 1 < M <= sqrt(N). We need not go higher than sqrt(N) because at least one factor of a pair that multiplies to give N must be less than or equal to sqrt(N). You can go higher if calculating the square root is complicated but you are guaranteed to not mark N as composite after that point.

[bryanirvine]

This was the precise problem I've been trying to wrap my head around in DP; Thank you!

[Tasarran]

When you make the lookup table, you can disregard results that are less than the number of dice, not just results less than one

[anthonymerle]

Not sure if I'm right, but the idea of using a lookup table for already computed results looks a lot like the "memoization" aspect of functional programming languages

[kenhaley]

As a test, I coded this in Python both ways: Top-down using recursion, and bottom-up using the lookup table. The iterative method was incredibly faster. It found the answer to 100 dice and total of 500 in about 50 milliseconds. The top-down approach never finished.

[christopherg]

The best way to solve any computation problem: Looking it up in a list
The second best way to solve any computation problem: Finding a efficient way to make a list.

[jelen]

this inspired me to make a function in my python package that can calculate the number of ways you can throw so the number is the same as the number you wanted to throw

[ZeroSleap]

This recursion optimization of saving previously calculated values, if i remember correctly, is called memoization(not a typo or baby way to say memorization).

[ronaldbell]

Excellent discussion. I had a hard time understanding the algorithm and eventually had to write it out myself. The problem for me was that for you the dice are all the same, so rolling a 2 on one die and a 1 on the other to get 3 was the same as rolling a 1 on the first die and a 2 on the other. But to me the dice were different, and so that was *two* different ways of rolling a 3 rather than *one*. Interesting how thinking of the problem space in a slightly different way make the solution harder to understand. The solution was fascinating though. Thanks.

[h_]

I solved this problem using the multinomial theorem to expand (x + x^2 + ... + x^6)^m which involves finding all weak compositions of m into 6 parts. Given this composition, lets say its [3, 0, 2, 1, 0, 0] find the coefficient for (x^1)^3 * (x^2)^2 * x^3 using the multinomial coefficient (m:3, 2, 1). Repeat for all compositions, and the result in standard form tells you for each exponent of x the number of ways to sum to that number.

[MeriaDuck]

2:25 I wondered how fast that would actually be. For ten dice my brute force attempt took less than a second to create the full histogram, do not underestimate the power of brute force ;-)
32 seconds for twelve dice and 192 seconds for thirteen. Of course this grows very very quickly. Brute forcing anything beyond that is kinda hopeless. 30 dice would be quite impossible to brute force.

[jakesto]

I'm taking a discrete structures class right now, so I figured out a way to calculate the same thing using combinatorics and multisets. I don't know whether it's worth it, because factorials take time to calculate, but it works pretty well and isn't *that* hard to understand.

[makkusaiko]

"We'll need somewhere to store it"
Me internally: "Hashmap, throw a hashmap at it"

[GroundThing]

There are no doubt even better solutions than this, but you can cut down on the number of table calls you need to do by considering the chance of rolling a total of M on N dice is the sum of the product of the chances of rolling M-x and x over N/2 dice (with x ranging between N/2 and 3N, being the minimum and maximum rolls on N/2). With some adjustments for odd Ns and the like, this makes it so you mostly only have to check the powers of 2

[fredoverflow]

I like how your lookup table is an actual, wooden table 😊

[nanke]

I like the eerie pascal table that seems to form in the top row, and the symmetry, there must be some ways to skip accessing most cells