剑指offer-面试题60-n个骰子的点数-动态规划

/*

题目：

	计算n个骰子，出现和s的概率。

*/

#include<iostream>

#include<cstdlib>

#include<stack>

#include<cstring>

#include<vector>

#include<deque>

#include<cmath>

using namespace std;

//将骰子分为1和n-1两堆

void getProbability(int n){

    //存储上一轮不同的和s，出现的次数，n=1时，各出现1次。

    int pre_probility[6*n+1] = {1,1,1,1,1,1,1};

    //存储当前轮不同的和s，出现的次数

    int probility[6*n+1] = {0};

    //从掷2颗骰子算起，循环到掷n个骰子为止

    for(int i = 2; i <= n; i++){

        //计算不同的和j，出现的次数。j最小为i，最大为6n

        for(int j = i; j < 6*n+1; j++){

            //计算和j出现的次数为第i堆从1~6，和前i-1堆，j-（1~6）出现的次数

            for(int k = 1; k <= 6; k++){

                //注意j-k,最大为6(i-1),最小为i-1

                if(j-k <= 6*(i-1) && j-k >= i-1)

                    probility[j] += pre_probility[j-k];

            }

        }

        for(int j = i; j < 6*i+1; j++){

            pre_probility[j] = probility[j];

            probility[j] = 0;

        }

    }

    int count = 0;

    for(int i = n; i < 6*n+1; i++){

        count += pre_probility[i];

        cout<<(double)pre_probility[i]/pow(6,n)<<endl;

    }

    cout<<count<<endl;

}

int main()

{

    getProbability(3);

}