n个骰子的点数和为s的概率集合输出（Java）

问题描述：

把n个骰子仍在地上，所有骰子朝上一面的点数之和为s,输入n,打印出s的所有可能出现的概率

问题分析：

这是一道应用动态规划思想的题目，而动态规划最难的就是要找最优子结构。并采取一种称为备忘录的方法避免重复计算。因为备忘录方法为每个解过的子问题建立了备忘录，以备需要时参看，避免了相同子问题的重复求解。

最优子结构：

F(n, s) 表示n个骰子点数和为s的种数，n表示骰子个数，s表示n个骰子的点数和
F(n, s) = F(n-1, s-1) + F(n-1, s-2) + F(n-1, s-3) + F(n-1, s-4) + F(n-1, s-5) + F(n-1, s-6)

public class Probability {  

    public void printProbability(int number) {  //number为骰子的个数
        if (number < 1)  return;  

        int g_maxValue = 6;    //骰子的最大点数为6

        int[][] probabilities = new int[2][];   //定义两个数组用于保存前一循环的数据供下一阶段使用
        probabilities[0] = new int[g_maxValue * number + 1];  
        probabilities[1] = new int[g_maxValue * number + 1];  

        int flag = 0;    //用于表示轮数交换的表示，当前阶段的信息做下一阶段的输入，上一阶段的信息清空，表示下阶段的输出
        //初始化骰子为1时，F(1,s) 的频数
        for (int i = 1; i <= g_maxValue; i++)  
            probabilities[0][i] = 1;  

        // n表示s要加上第n个骰子朝上的数，也表示n轮大循环
        for (int n = 2; n <= number; ++n) {  

            // 归零操作，因为随着s的变大，F(1,0), F(2,1), F(3,2),...,F(6,5)都不会出现，但是前面计算出现过F(1,1), F(2,2), F(3,3),...,F(5,5)，
            //因为我们是交替使用前一个数组，所以必须作归零处理
            for (int i = 0; i < n; ++i)  
                probabilities[1 - flag][i] = 0;  

            //第n轮数据之和为s∈[n, g_maxValue*n]，然后计算每一个s的频数
            for (int s = n; s <= g_maxValue * n; ++s) {  
                probabilities[1 - flag][s] = 0;   //  第n轮第n个数据初始化为0

                //计算F(n, s) = F(n-1, s-1) + F(n-1, s-2) + F(n-1, s-3) + F(n-1, s-4) + F(n-1, s-5) + F(n-1, s-6) 
                for (int j = 1; j <= s && j <= g_maxValue; ++j)  
                    probabilities[1 - flag][s] += probabilities[flag][s - j];  
            }  
            flag = 1 - flag;  
        }  
        double total = Math.pow(g_maxValue, number);  
        for (int i = number; i <= g_maxValue * number; i++) {  
            double ratio = (double) probabilities[flag][i] / total;  
            System.out.println(i);  
            System.out.println(ratio);  
        }  
    }  
}