【墨鳌】【动态规划~概率DP】

题目链接
题解链接

解题思路

• 用 \(n\) 个??投掷出点数和为 \(x\) 的概率为 \(p(n,x)\)

• 初始条件为：

复杂度

• 时间复杂度 \(O(n^2)=O(n\times 6\cdot n\times 6)\)
• 空间复杂度 \(O(n^2)=O((n+1)\times(6\cdot n+1))\)

代码

class Solution {
public:
    vector dicesProbability(int n) {
        vector>dp(n+1,vector(6*n+1,0.0));
        dp[0][0]=1.0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=6*n;j++)
                for(int k=1;k<=6;k++)
                    if(j-k>=0)dp[i][j]+=dp[i-1][j-k]/6.0;
        return vector(begin(dp[n])+n,end(dp[n]));
    }
};