剑指offer上43题

n个骰子，朝上一面的点数之和为S，求S的所有可能的值的概率

有两种方法 1.递归

2.动态规划 f(n) = f(n-1)+f(n-2)+....+f(n-6);

贴代码：

package testAbstractClass;public class xiecheng {    //有n个骰子，所有朝上的点数之和为S 求S的所有可能值出现的概率。    public static int six=6;    public static void main(String args[]){        //printpro(2);        printProbability(2);            }         //以下为递归解法    public static void printProbability(int n){        if(n<1) return;        int maxsum = n*six;        int minsum = n*1;        //将和为s的出现次数放在s-n个位置 index=s-n;index一共是0-5n        int [] mark_num = new int [maxsum-minsum+1];//自动初始化为0；        probability(n, mark_num);               int total = (int) Math.pow(six, n);//总共的可能数目为6^n        for(int i=n;i<=maxsum;i++){            double ratio = (double)mark_num[i-n]/total;            System.out.println("和为"+i                    +"出现的概率是"+ratio);        }    }    //获取所有的可能 并将出现的次数存在一个5n+1的数组中；    public static void probability(int n,int [] mark_num){        for(int i =1;i<=six;i++){            probability(n,n,i,mark_num);        }    }    //递归实现 将n个骰子，目前递归到序号，目前的和，以及标记数组传进来。当序号递归6次 就完成一次记录 ，将对应位置上的值加1    public static void probability(int original,int current,int sum,int [] mark_sum){        if(current==1) mark_sum[sum-original]++;        else{            for(int i=1;i<=six;i++){                probability(original,current-1,i+sum,mark_sum);            }        }        }         }

 

第二种方法是动态规划，记录前一轮状态中的骰子的值 

/**     * 解法2 动态规划法；用两个数组存储骰子点数的每一个总数出现的次数： 数组的第n个数字达标骰子和为n出现的次数，     * 在下一轮循环中，加上一个新的骰子,此时和为n的骰子出现的次数应该等于上一轮骰子点数为n-1，n-2,n-3,n-4,n-5,n-6的次数总和。     * f(n) = f(n-1)+...f(n-6);     */    public static  void printpro(int n){        int [][] pro =  new int [2][six*n+1];                        int flag =0;        //第一个骰子的状态 就是dp的出示状态        for(int i=1;i<=six;i++) pro[flag][i] =1;        //第二个骰子到第n个骰子        for(int j=2;j<=n;j++){            //将前0-j置零 因为j个骰子 点数最少都是j*1            for(int i=0;i

第二种方法时间上效率较高。只比第一种方法多费了o（n）的空间。

’