lCOF-60

​ # 剑指 Offer 60. n个骰子的点数

At first use recursion:

var twoSum = function(n) {
    let m = new Map();
    dfs(m, 0, n,0);
    let sum = 0;
    let ret= [];
    for(let [k, v] of m.entries()) {
        sum+=v;
        ret.push(v);
    }
    for( let i = 0; i< ret.length; ++i) {
        ret[i] = ret[i] / sum
    }
    return ret;
};

var dfs = function(m, start, n, sum) {
    if(start===n) {
        if(m.has(sum)) {
            m.set(sum, m.get(sum)+1);
        } else {
            m.set(sum, 1);
        }
        return;
    }
    for(let i=1; i<=6; ++i) {
        sum+=i;
        dfs(m, start+1, n, sum);
        sum-=i;
    }
}

Unfortunetely, rum time error.

Refer to the official answer, we could use iterative method.

var twoSum = function(n) {
    if(n<1) return []
    const res = [0, 1, 1, 1, 1, 1, 1];
    for(let i = 1; i<n; ++i) {//control times for simulation
        for(let j = 6*n; j>0; j--) {//control simulation
            res[j] = res.slice(Math.max(0, j-6), j)
            .reduce((acc, cur)=>acc+cur, 0);
        }
    }
    return res.slice(1).map(num=>num/Math.pow(6,n)).filter((i)=>i!=0);
};

The time complexity is O(n²), and space complexity is O(n).