package JianZhiOffer60;

import java.util.Arrays;

/**
 * @author ：dazhu
 * @date ：Created in 2020/4/19 17:44
 * @description：
 * @modified By：
 * @version: $
 */
public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.twoSum(2)));
    }
}
class Solution {
    /**
     *
     * @param n 输入侄子个数
     * @return 返回概率
     * 状态定义：dp的行数代表当前侄子个数，列数代表当前侄子的和值，该位置存放的数代表种类数
     * 状态转移：dp[n][m]代表n个侄子和为m的种类数，则有dp[n][m] = dp[n-1][m-1] +dp[n-1][m-2]+dp[n-1][m-3] +dp[n-1][m-4]+dp[n-1][m-5] +dp[n-1][m-6]
     * 如果超过了dp数组范围，则为0。
     * 控制方向：循环dp数组从上到下，从左到右。
     */
    int[][] dp ;
    public double[] twoSum(int n) {
        //初始化dp数组
        dp = new int[n+1][];
        dp[1] = new int[]{0,1,1,1,1,1,1};
        double totalKinds = Math.pow(6,n);
        //按照循环方向在状态转移方程下进行计算。
        for(int i=2;i<n+1;i++){
            //由于每一行的长度要根据当前侄子可能出现的种类数，来判断
            dp[i] = new int[6*i+1];
            for(int j=i;j<6*i+1;j++){
                dp[i][j] = fn(i-1,j-1)+fn(i-1,j-2)+fn(i-1,j-3)+fn(i-1,j-4)+fn(i-1,j-5)+fn(i-1,j-6);
            }
        }
        //创建结果概率数组
        double[] result = new double[5*n+1];
        //在dp二维数组中计算结果数组
        for(int i=0;i<5*n+1;i++){
            result[i] = dp[n][i+n]/totalKinds;
        }
        return result;
    }

    /**
     *
     * @param n 当前侄子数
     * @param m 当前侄子之和
     * @return 当前对应的种类数
     */
    public  int fn(int n,int m){
        //如果m小于0或者超过当前行的范围，则直接返回0
        if(m<0||m>=6*n+1){
            return 0;
        }
        //否则返回当前位置的值即可，即当前种类数
        else{
            return dp[n][m];
        }
    }
}