一道状态较多的概率DP，想要表示所有的状态显然要拓展几个维度表示九堆牌当前的状态 。

但是这么写太复杂，所以我们不妨用一个vector来储存状态，将dp数组用一个map来表示，即 map ,double> d; 利用vector可以作为函数参数传递这个优点，将大大节省代码量 。

概率很好求，在每一次迭代中，寻找所有可以转移的状态数tot，那么状态转移就是d[i] = sum(d[i-1])/tot 。 也就是全概率公式 。

递归边界是当所有牌都被摸走了，返回1（因为概率总和为1）。

全概率公式说白了就是每一部分都不相交，且相加恰好为1 。 其实对于概率DP，所求的概率一定是全概率的，因为DP所表示的每一个状态的概率是一个固定的值，且相加为1。

由此也可以看出，如果运用动态规划，那么必须满足：状态经过多次转移之后不会回到以前的状态 。

细节参见代码：

#include
  
   
using namespace std;
map
   
     ,double> d; char s[15][15][5]; double dp(vector
    
      cnt,int c) { if(c == 0) return 1; if(d.count(cnt)) return d[cnt]; double sum = 0; int tot = 0; for(int i=0;i<9;i++) if(cnt[i]>0) for(int j=i+1;j<9;j++) if(cnt[j]>0) if(s[i][cnt[i]-1][0] == s[j][cnt[j]-1][0]) { tot++; cnt[i]--; cnt[j]--; sum += dp(cnt,c-2); cnt[i]++; cnt[j]++; } if(tot == 0) return d[cnt] = 0; return d[cnt] = sum/tot; } bool read_input() { for(int i=0;i<9;i++) for(int j=0;j<4;j++) if(scanf(%s,s[i][j]) != 1) return false; return true; } int main() { while(read_input()) { vector
     
       cnt(9,4); d.clear(); printf(%.6f ,dp(cnt,36)); } return 0; }