面试题60：n个骰子的点数

??可以很轻松地想到用回溯法进行暴力枚举，但复杂度很高O(6^n)，肯定会超时，所以可以类比为斐波那契数列的形式：\(f(n) = f(n-1)+f(n-2)+f(n-3)+f(n-4)+f(n-5)+f(n-6)\)。采用类似动态规划的方法（其实和斐波那契一样，并不严格是动态规划）。

回溯法暴力枚举C++

int g_maxValue = 6;

// 暴力递归，复杂度很高O(6^n)，绝对超时
void Probability(int original, int current, int sum, int* pProbabilities){
    if(current == 0){
        pProbabilities[sum - original]++;
        return ;
    }

    for(int i = 1; i <= g_maxValue; ++i)
        Probability(original, current - 1, i + sum, pProbabilities);
}


void PrintProbability_Solution1(int number){
    if(number < 1)
        return;

    int maxSum = number * g_maxValue;
    int* pProbabilities = new int[maxSum - number + 1];
    for(int i = number; i <= maxSum; ++i)
        pProbabilities[i - number] = 0;

    Probability(number, number, 0, pProbabilities);

    int total = pow((double)g_maxValue, number);
    for(int i = number; i <= maxSum; ++i){
        double ratio = (double)pProbabilities[i - number] / total;
        printf("%d: %e\n", i, ratio);
    }

    delete[] pProbabilities;
}


int main(int argc, char* argv[]){

    PrintProbability_Solution1(6);

    return 0;
}

面试题60：n个骰子的点数

原文：https://www.cnblogs.com/flyingrun/p/13574456.html