1467. 两个盒子中球的颜色数相同的概率 动态规划

是鹅好甜

题目意思


求 种类相同数目相同/数目相同 的值
方法：动态规划

实际上需要关心种类和数目两个点，假设A盒子比B盒子多分一个计算为 +1, 反过来计算为 -1，那么种类和数目范围分别为 -8 到 8， -48 到 48

假设某种颜色有 5 个球，那么可能有下面几种情况：


A 分 0 个，B 分 5 个，A 的种类就比B少选1种计算为 -1，数目比 B 少算 5 种计算为 -5

A 分 1 到 4 个， B 分 4 到 1 个，两个种类差距数目不变，数目差距为两者的差 selectA - (total-selectA)

A 分 5 个，B 分 0 个，A 的种类数相对 B 多得到 1 个，数目 比 B 多得到 5 个


两个盒子中球的数目相同为所有可能性数目之和值A；两个盒子中球种类数相同为选到最后种类数目差都为0的数目为B，B/A即为答案