每次从包装中取出一块巧克力并放在桌子上。如果桌子上有两个相同颜色的巧克力，则将这两个丢掉。
如果包中有C种颜色的巧克力（颜色均匀分布），从包装中取出N个巧克力后，桌子上确实有M个巧克力的概率是多少？
对于每种情况，存在三个非负整数：C（C
首先，判断边界条件，如果取出0个巧克力，那么桌子上剩余0个巧克力的概率是多少？？？很简单，dp[0][0] = 1;
另外，针对输入的c，n，m进行非法判断，即概率为0.000的直接输出就好了
dp[i][j]表示前i次操作(即取出i个巧克力)后，桌上出现j个巧克力的概率。试想，如果i+j是奇数会是什么情况？
dp[i][j]是等于0的(不可能出现的情况)。为什么不可能出现呢， 因为每次取出的球都会现放到桌上比较，如果没有重复的颜色，则桌子上球数+1,如果有重复，将重复的两个球都拿掉，也就是i的次数首先加到m上，此刻的m要么不变，要么-2,不会出现奇数的情况。所以dp[i][j]中i+j为奇数则概率是0
可以手动模拟验算下。
那么，状态转移方程怎么来呢？？因为 要 么取到的球和桌子上球的颜色不重复，即 dp[i-1][j-1] * (c-j+1.0)/c; 就是在前面拿出i-1个巧克力后，桌子剩余j-1个巧克力的概率上，乘上这次取出的巧克力与桌子上巧克力颜色不重复的概率， c-j+1.0,表示颜色总数减去桌上的不同颜色的，剩余的也是不同颜色的，再除以c就是对应的取出不同颜色的概率了。
要么 取出的球和桌上某个球的颜色相同，要一起拿走，方程是这样：dp[i-1][j+1]*（j+1.0)/c ，j+1/c，即取出的球的颜色和桌上的球的某个颜色相同了
dp[i][j]将二者加起来即可
另外，在对很大的n进行计算时，可以将其看成一个较小的n，因为很大的n对应的概率和较小的数m的概率只有小数点后好几位才会不同，所以可以转换下
Original: https://www.cnblogs.com/ygsworld/p/11329954.html
Author: 回忆酿的甜
Title: POJ1322Chocolate–概论DP
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/582130/
转载文章受原作者版权保护。转载请注明原作者出处！