剑指offer 60 n个骰子的点数

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

这道题使用动态规划的问题, 动态的是投出了几个骰子

创建数组count[ i ][ j ] 其中i表示投出的骰子总数, j表示数字加和. count表示出现的次数.

投出下一个骰子的时候, 可能的数字和是上一个骰子投出[ j - 1], [ j - 2 ], ........, [ j - 6 ] 的次数之和

最终查看count[ n - 1][ n ]~ count[n - 1][ 6 * n] 就是各个结果, 最后和总次数做除法.

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

double* twoSum(int n, int* returnSize){
    *returnSize = 5 * n + 1;
    double *ret = malloc(sizeof(double) * (*returnSize));

    int **count = malloc(sizeof(int*) * n);
    for(int i = 0; i< n; i++)
    {
        count[i] = malloc(sizeof(int) * 6 * n);
        memset(count[i], 0, 6 * n *sizeof(int));
    }

    //第一个骰子之后, 总和是i的次数
    for(int i = 0; i < 6; i++)
    {
        count[0][i] = 1;
    }

    //第二个骰子
    for(int i = 1; i <n; i++)
    {
        //总和是j(因为两个骰子综合肯定大于1)的次数, 是上一个骰子点数为j-1 ~j-6次数之和
        for(int j = 1; j <6 * n; j++)
        {
            for(int k = 1; k <=6; k++)
                if(j - k >= 0)
                    count[i][j] +=count[i-1][j-k];
        }
    }


    for(int i = 0; i< (*returnSize); i++)
    {
        ret[i] = (double)count[n-1][i + n - 1]/pow(6, n);
    }
    for(int i = 0; i<n ; i++)
    {
        free(count[i]);
    }
    free(count);
    return ret;
}

时间复杂度: N* N * 6
空间复杂度: N * N * 6