I am stuck on this problem from CSES. My dp approach is dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + …dp[i-1][j-6] (till j-x is valid) where i is the number of throws and j is the sum. In the end I sum over dp[n][a] till dp[n][b] for numerator and denominator dp[n][n] to dp[n][6*n]. I am not passing testcases.
Here is my code . Please help.
1 Like
Integer overflow. The numbers are on the order of 6^n.
But here n<=100 and we are only concerned with the sum of values. So max value can be 600.
Also do you have any other ideas on approaching the problem?
6^n not 6n
Are you sure you know what you are doing?
According to you dp_{i,j} denotes number of ways to get sum of j in i tosses. Since you sum over all valid j, the denominator is the number of possible sequence of n tossed. So your denom will be 6^n, which is 6^{100}, much more than any inbuilt integer type.
Ahh I understood it. You are right. What is the approach for the denominator?
I think you are complicating the solution. This is a simple 1-d DP problem. Take a look at my solution.
https://cses.fi/problemset/result/925850/
I cant view the code. Can you post it here or explain the logic?
Store probability instead of number of ways on your dp array. So you want to also divide by 6 in your dp relation.
2 Likes
Space saving dp is still 2d dp.
Thanks 