20. Dice Sums

Description
Throw n dices, the sum of the dices' faces is S. Given n, find the all possible value of S along with its probability.

Example
Given n = 1, return [ [1, 0.17], [2, 0.17], [3, 0.17], [4, 0.17], [5, 0.17], [6, 0.17]].

思路：直接DP即可。不需处理精度。

Code：

class Solution {
public:
    /**
     * @param n an integer
     * @return a list of pair<sum, probability>
     */
    vector<pair<int, double>> dicesSum(int n) {
        // Write your code here
        double a[100][600]={0};
        for(int i=1;i<=6;i++){
            a[1][i]=1.00/6;
        }
        for (int i = 2;i <= n;i++){
            for (int j = i;j<=6 * n;j++){
                double temp = 0;
                for (int k = 1;k<=6;k++){
                    temp += a[i - 1][j - k] * a[1][k];
                }
                a[i][j] = temp;
            }
        }
        vector<pair<int,double>> ans;
        for(int i=n;i<=6*n;i++){
            pair<int,double> temp(i,a[n][i]);
            ans.push_back(temp);
        }
        return ans;
    }
};