The following code is for this problem.

Input

The input consists of a single line with three integers n
, s
, and k
(1 ≤ n ≤ 10,000, 1≤ k ≤ s ≤ 500
). n
is the number of throws, k
the number of different numbers that are needed to win and s
is the number of sides the die has.

Output

Output one line with the probability that a player throws at least k
different numbers within n
throws with an s
-sided die. Your answer should be within absolute or relative error at most 10^{−7}
.

Sample Input 1

3 3 2

Sample Output 1

0.888888889

Sample Input 2

3 3 3

Sample Output 2

0.222222222

This program used 0.89s to pass all test cases. But I find other people use Java can achieve ~0.20s. How can I improve my code?

The idea is to establish a table for the recursive call to look up previously calculated the value.

import java.util.*;

public class Dice

 static double table;

 public static double game(int s, int r, int d)
 
 if(table[r][d] != -1) return table[r][d];
 double a = (1 - (double)d/(double)s) * game(s, r - 1, d + 1);
 double b = ((double)d/(double)s) * game(s, r - 1, d);
 double sum = a + b;
 table[r][d] = sum;
 return sum;
 

 public static void main(String args)
 
 Scanner in = new Scanner(System.in);
 int n = in.nextInt();
 int s = in.nextInt();
 int k = in.nextInt();
 table = new double[n+1][n+1];

 for(int i = 0; i < n+1; i++)
 for(int j = 0; j < n+1; j++)
 table[i][j] = (double)-1;

 for(int i = 0; i < n+1; i++)
 for(int j = 0; j < n+1; j++)
 if(i + j < k)
 table[i][j] = (double)0;

 for(int j = 0; j < n+1; j++)
 for(int i = k; i < n+1; i++)
 table[j][i] = (double)1;

 System.out.println(game(s, n, 0));
 
 

Don't Repeat Yourself

Your main() function starts with 3 loops to initialize your table array. There are several problems here. First, it writes past the end of the array. If your array has n + 1 elements, then you can only write to 0 through n. Element n + 1 is out-of-bounds. So each of your loops is writing to one element of the next row, and then one extra row at the end, and one element past that, too. The loops should only go from 0 to n. This happens to work because you later read past the end of the array, too. If you're going to do that, you need to allocate n + 2 rows and columns.

Next, you're writing several elements 3 times. You can combine these 3 loops into 1 and do far less initialization. Further, you should use braces around all loop and conditional bodies because there's the potential to create errors in the future if you don't.

Also, you've switched i and j in the last loop which is highly confusing and could easily be missed by a reader.

Here's how I would write your initialization code:

table = new double [ n + 2 ][ n + 2 ]
for (int i = 0; i < n + 1; i++)

 for (int j = 0; j < k; j++)
 
 if (i + j < k)
 
 table [ i ][ j ] = 0.0;
 
 else
 
 table [ i ][ j ] = -1.0;
 
 

 for (int j = k; j < n + 1; j++)
 
 table [ i ][ j ] = 1.0;
 

Now no element should be touched more than once, no elements past the end of the array should be written to, and no array indexes are flipped.

You're also calculating (double)d / (double)s twice. You should calculate it once and re-use this value.

Naming

You should choose better names for your variables. i and j are fine for loop indexes as they are commonly used that way and nobody will be confused by them. However, I'd rename n, s, and k. I'd name n something descriptive like numThrows; k should be something like numNeeded, and s should be numSides.

Likewise, s, r, and d are not very helpful names for the arguments to game().

Speed

I haven't profiled your code, which is the real way to find out which parts are slow. I have seen many cases where casting variables from one type to another causes significant slowdowns. Since the bulk of your game() function is either calling itself or casting values, I recommend just making the arguments to the function be double to begin with. Of course, you can't use a double as an index into an array. So you could either pass the r and d values as both doubles and ints.