## Friday, February 19, 2016

### LintCode 30- Dice Sum

http://www.lintcode.com/en/problem/dices-sum/
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]]`.

1.     public List<Map.Entry<Integer, Double>> dicesSum(int n) {
2.         List<Map.Entry<Integer, Double>> res = new LinkedList();
3.         double[][] dp = new double[n + 1][6 * n + 1];
4.         for (int i = 1; i <= 6; i++) {
5.             dp[1][i] = 1.0 / 6.0;
6.         }
7.         for (int i = 2; i <= n; i++) {
8.             for (int j = i; j <= 6 * i; j++) {
9.                 for (int k = 1; k <= 6; k++) {
10.                     if (j > k) {
11.                         dp[i][j] += dp[i - 1][j - k];
12.                     }
13.                 }
14.                 dp[i][j] /= 6.0;
15.             }
16.         }
17.         for (int i = n; i <= 6 * n; i++) {
19.         }
20.         return res;
21.     }
https://zhengyang2015.gitbooks.io/lintcode/dices_sum_20.html

``````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++){
}

return result;
}``````
``` ```

Buttercola: Indeed: Sum Dice Possibility

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;
}