写一个函数float sumPossibility(int dice, int target)，就是投dice个骰子，求最后和为target的概率。因为总共的可能性是6^dice，所以其实就是combination sum，

求dice个骰子有多少种组合，使其和为target。先用brute force的dfs来一个O(6^dice)指数复杂度的，然后要求优化，用dp，最后结束代码写的是两者结合的memorized search吧

Solution:A classic backpack problem. Using DP would solve the problem.

/**

/**
 * Created by 1000132937 on 3/25/2018.
 */
public class DiceSum {
    private int totaldfs = 0;
    // dfs to calculate how many possible ways to have target
    public float SumWithDFS(int dice, int target) {
        int total = (int)Math.pow(6, dice);
        dfs(dice, target);
        return (float) totaldfs / total;
    }

    private void dfs(int dice, int target){
        if (dice == 0 && target == 0) {
            totaldfs++;
            return;
        }
        if (dice == 0 || target <= 0 ) {
            return;
        }

        for (int i = 1; i<= 6; i++) {
            dfs(dice - 1, target - i);
        }
    }

    // DP
    //
    public float diceSumDP(int dice, int target) {
        int total = (int) Math.pow(6, dice);
        int[][] dp = new int[dice + 1][target + 1];
        //initial
        for (int i = 1; i < Math.min(6, target); i++) {
            dp[1][i] = 1; // one dice, target i has one possible
        }
        for (int i = 2; i <= dice; i++) {
            for(int j = 1; j <= target; j++) {
                for (int k = 1; k <= 6 && k < j; k++) {
                    dp[i][j] += dp[i - 1][j - k];
                }
            }
        }
        return (float)dp[dice][target]/total;
    }
}