The following code is for this problem
This program used 0.89s to pass all test cases. But I find other people use Java can achieve ~0.20s. So how to 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)); } }