60. points of N dice

The finger of the sword Offer 60. n The number of dice

Ideas ： Dynamic programming

hypothesis n-1 The solution of dice is f(n-1), Now add a dice ,n The sum of dice points is x Probability f(n,x) by

$f(n,x)=\sum _{i=1}^{6}f(n-1,x-i)\times \frac{1}{6}$

If calculated according to this formula , There will be an array out of bounds problem .

therefore , Consider by f(n-1,x) deduction f(n-1,x+i)

class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<double> dp(6,1.0/6.0);
        for(int i=2;i<=n;++i){
            vector<double> tmp(5*i+1,0);
            for(int j=0;j<dp.size();++j){
                for(int k=0;k<6;++k){
                    tmp[j+k]+=dp[j]/6.0;
                }
            }
            dp=tmp;
        }
        return dp;
    }
};

Time complexity O($n^2$) The calculated number of cycles is $6\times 6,11\times 6,[5(n-1)+1]\times 6$ The overall time complexity is $O((6+5(n-1)+1)\times (n-1)/2)$, namely O($n^2$)

Spatial complexity O(n) need tmp Auxiliary array