数据结构练习（32）n个骰子的点数

http://zhedahht.blog.163.com/blog/static/254111742009101524946359/

思路：

简单的动态规划，利用滚动数组会节省内存。

#include <iostream>
#include <cmath>
using namespace std;

const int MAX_VALUE = 6;

void SolveProbability(int n)
{
    int* dp[2];
    int maxd = n * MAX_VALUE + 1;
    dp[0] = new int[maxd];
    dp[1] = new int[maxd];

    for (int i = 0; i < maxd; ++i)
        dp[0][i] = dp[1][i] = 0;

    int flag = 0;
    dp[0][0] = 1;

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < maxd; ++j)
        {
            dp[1-flag][j] = 0;
            for (int k = 1; k <= j && k <= MAX_VALUE; ++k)
                    dp[1-flag][j] += dp[flag][j-k];
        }
        flag = 1 - flag;
    }

    double total = pow((double)MAX_VALUE, n);

    for (int i = n; i < maxd; ++i)
    {
        if (dp[flag][i])
        {
            double ratio = (double)dp[flag][i] / total;
            cout << i << ": " << ratio << endl;
        }
    }
    delete[] dp[0];
    delete[] dp[1];
}

int main()
{
    SolveProbability(2);
    return 0;
}