I was solving a problem, where one part of it was the following:
"Given a m-sided dice ([1,m] values) that will be rolled n times, calculate the possibility that the total sum of rolls will be higher than b"
Initially, I implemented a naive exponential solution, discovering the whole state space (DFS-like). Then, I realised that this algorithm repeats the calculation for a given number of remaining rolls and current sum. So, I optimised it, saving these calculations and using them later. For example, let's say we have a 4-sided dice that will be rolled 2 times (m=4, n=2). The below image shows the state space:
With green color are the values that were cached from previous computations and will be returned directly from memory. With red color are the values that will be normally computed. I have been trying to calculate the complexity of the algorithm:
- The initial algorithm, where there is no "caching" of values, has obviously an exponential complexity of
The iterations needed for the optimised algorithm follow the below pattern:
For (m=4,n=2): 11 = 4 + 7 = 4 + [(4*2)-1]
For (m=4,n=3): 21 = 4 + 7 + 10 = 4 + [(4*2)-1] + [(4*3)-2]
For (m=4,n=4): 34 = 4 + 7 + 10 + 13 = 4 + [(4*2)-1] + [(4*3)-2] + [(4*4)-3]
This seems to be a mathematical sequence, but I can't calculate the exact formula. Any help much appreciated.