[数据结构与算法]对一道记忆化搜索题目的思考（CSP软件能力认证202109T4）

暴力DFS（超时）

• 搜索每个事件发生概率，按期望的定义求解。
• 示例的搜索树：
  
• 如图，根节点开始搜索，选择抽取A卡或B卡。在子节点重复抽取原先的A卡或B卡，或抽得一张新卡。持续进行。dfs求解结果实际上对应根到阴影结点对应的路径长度乘该条路径上所有转移的概率。

记忆化搜索

Motivation

• 假设3张卡牌A,B,C，先抽A，再抽B，到达某一结点往下dfs；和先抽B，再抽A，到达某一结点往下dfs；需要进行重复搜索
• 能否用某种方式记录这些状态？

状态记录

• 体会搜索树，记录搜索树上结点的状态即可。
• 当手里的钱和手里有的卡牌完全相同时，无论上游进行何种搜索下游的搜索都是完全一致的。即这两者可以唯一标识一个结点。
• 令$dp[state][money]$表示当前收集卡牌状态state时，手上有money颗硬币，用于标识搜索树上每个结点.为其到后代叶节点概率加权抽样次数之和。
• 搜索树上的回溯用于计算。

#include <iostream>
#include<vector>
#include<map>
#include<string>
#include<set>
#include<algorithm>
#include<queue>
using namespace std;
double dp[65535][80];



//状态为i，手上j枚硬币时的累计
double dfs(int i,int j,int n,int o ,double dp[65535][80],double p[],int one[])  //状压dp
{
    if(dp[i][j] > 0)
        return dp[i][j];
    if(one[i] == n || j >= o * (n - one[i]))
    {
        dp[i][j] = j + one[i];
        return dp[i][j];
    }
    //下游结点
    dp[i][j] = 0;
    for(int k  =0 ;k<n;k++)
    {
        if((i >> k) & 1)  //可以重复抽取
        {
            dp[i][j] += p[k] *dfs(i,j+1,n,o,dp,p,one);
        }
        else
            dp[i][j] += p[k] * dfs(i | (1 << k),j,n,o,dp,p,one);
    }
    return dp[i][j];
}





//维护非零段的个数
int main()
{
    int n,k;
    cin >> n >> k;
    double p[n];
    int m = 1 << n;
    for(int i = 0;i<n;i++)
        cin >> p[i];
    for(int i  = 0;i<m;i++)
        for(int j = 0;j<2 + (n - 1) * k;j++)
        {
            dp[i][j] = -1;
        }
    double ans = 0;
    int one[1 << n];
    for(int i = 0;i<1 << n;i++)
    {
        one[i] = 0;
        int q = i;
        while(q > 0)
        {
            one[i] += q & 1;
            q = q >> 1;
        }
    }
    ans = dfs(0,0,n,k,dp,p,one);
    //for(int i = 0;i<1 << n;i++)
      //  for(int j = 0 ; j < 2 + (n - 1) * k;j++)
        //    cout << "dp" << i << " " << j << "=" << dp[i][j] << endl;
    printf("%.10lf\n",ans);
    return  0;
}