http://www.lintcode.com/en/problem/dices-sum/
Buttercola: Indeed: Sum Dice Possibility
这个地里面经没看到过,写一个函数float sumPossibility(int dice, int target),就是投dice个骰子,求最后和为target的概率。因为总共的可能性是6^dice,所以其实就是combination sum,求dice个骰子有多少种组合,使其和为target。先用brute force的dfs来一个O(6^dice)指数复杂度的,然后要求优化,用dp,最后结束代码写的是两者结合的memorized search吧,面试官走的时候还说了句such a good solution。
public static float sumPossibility(int n, int target) {
if (n <= 0 || target <= 0) {
return 0;
}
int total = (int) Math.pow(6, n);
int[][] dp = new int[n + 1][target + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= target; j++) {
for (int k = 1; k <= 6; k++) {
if (j >= k) {
dp[i][j] += dp[i - 1][j - k];
}
}
}
}
return (float) dp[n][target] / total;
}
Read full article from Buttercola: Indeed: Sum Dice Possibility
Throw n dices, the sum of the dices' faces is S. Given n, find the all possible value of S along with its probability.
Notice
You do not care about the accuracy of the result, we will help you to output results.
Given
n = 1
, return [ [1, 0.17], [2, 0.17], [3, 0.17], [4, 0.17], [5, 0.17], [6, 0.17]]
.
二维数组dp[i][j]保存投掷i次得到和为j的概率,当前位置的概率为当前投掷1 ~ 6的情况下的前序概率和
- public List<Map.Entry<Integer, Double>> dicesSum(int n) {
- List<Map.Entry<Integer, Double>> res = new LinkedList();
- double[][] dp = new double[n + 1][6 * n + 1];
- for (int i = 1; i <= 6; i++) {
- dp[1][i] = 1.0 / 6.0;
- }
- for (int i = 2; i <= n; i++) {
- for (int j = i; j <= 6 * i; j++) {
- for (int k = 1; k <= 6; k++) {
- if (j > k) {
- dp[i][j] += dp[i - 1][j - k];
- }
- }
- dp[i][j] /= 6.0;
- }
- }
- for (int i = n; i <= 6 * n; i++) {
- res.add(new AbstractMap.SimpleEntry<Integer, Double>(i, dp[n][i]));
- }
- return res;
- }
用dp解决。dp[i][j]表示i个骰子一共得到j点的概率。要得到dp[i][j]可以考虑若最后一个筛子的点数为k(1~6),则前i-1个筛子一共得到的点数为j-k(因为i-1个筛子至少得到i-1点,所以j-k >= i - 1 => k <= j - i + 1)。所以只要把最后一个筛子为k的各种情况加起来最后再除以6即可(每多一个筛子概率要多除以一个6)。
状态函数:
dp[i][j] = dp[i-1][j-k] (i <= j <= 6 * i, k >= 1 && k <= j - i + 1 && k <= 6)
public List<Map.Entry<Integer, Double>> dicesSum(int n) {
List<Map.Entry<Integer, Double>> result = new ArrayList<Map.Entry<Integer, Double>>();
if(n < 1){
return result;
}
//初始化n=1的情况
double[][] matrix = new double[n + 1][6 * n + 1];
for(int i = 1; i <= 6; i++){
matrix[1][i] = 1.0/6;
}
for(int i = 2; i <= n; i++){
//i个筛子至少得到i点,至多得到6 * i点
for(int j = i; j <= 6 * i; j++){
//k表示最后一个筛子能取的点数
for(int k = 1; k <= 6; k++){
if(k <= j - i + 1){
matrix[i][j] += matrix[i - 1][j - k];
}
}
//相对i-1个筛子多了一个筛子,因此加和的每一项都要除以6
matrix[i][j] /= 6.0;
}
}
for(int i = n; i <= 6 * n; i++){
result.add(new AbstractMap.SimpleEntry<Integer, Double>(i, matrix[n][i]));
}
return result;
}
Buttercola: Indeed: Sum Dice Possibility
这个地里面经没看到过,写一个函数float sumPossibility(int dice, int target),就是投dice个骰子,求最后和为target的概率。因为总共的可能性是6^dice,所以其实就是combination sum,求dice个骰子有多少种组合,使其和为target。先用brute force的dfs来一个O(6^dice)指数复杂度的,然后要求优化,用dp,最后结束代码写的是两者结合的memorized search吧,面试官走的时候还说了句such a good solution。
public static float sumPossibility(int n, int target) {
if (n <= 0 || target <= 0) {
return 0;
}
int total = (int) Math.pow(6, n);
int[][] dp = new int[n + 1][target + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= target; j++) {
for (int k = 1; k <= 6; k++) {
if (j >= k) {
dp[i][j] += dp[i - 1][j - k];
}
}
}
}
return (float) dp[n][target] / total;
}
Read full article from Buttercola: Indeed: Sum Dice Possibility