// Dynamic Programming
public static double lostProb(int number) {
if(number > 21) return 1.0;
if(17 <= number && number <= 21) return 0.0;
// the maximum number is 16 + 10 = 26
// 17 ~ 21 wins, 22 ~ 26 lost
// state: dp[i] = probability to reach number i
double[] dp = new double[27];
// initialize
// note that number is less than 17
for(int i = number + 1; i <= number + 10; i++) {
dp[i] = 0.1;
}
// top-down function
for(int i = number + 2; i <= 26; i++) {
for(int j = Math.max(number + 1, i - 10); j < Math.min(i, 17); j++) {
dp[i] += dp[j] * dp[i - j];
}
}
// answer
return dp[22] + dp[23] + dp[24] + dp[25] + dp[26];
}
//*******************************************************