记忆化搜索与dp

Posted on Views:

剪枝

  1. 优化搜索顺序
  2. 排除等效冗余

记忆化搜索与DP

质数拆分 题意：将 \(2019\) 拆分为若干个两两不同的质数之和，一共有多少种不同的方法？注意，交换顺序视为同一种方法
代码中 \(N = 2019\)，\(prime\) 是预处理好的质数数组 ## 暴搜（不考虑剪枝\(O(N!)\) 因为不考虑先后顺序，所以用 start 来避免重复 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int ans = 0;
void dfs(int sum, int start)
{
    if(sum == N)    //已选的数的总和为N，找到一个解
    {
        ans++;
		return;
    }

	//从起始位置开始往后找
    for(int i = start; i < prime.size(); i++)
    {
        //由于数组是单调递增的，所以如果加上这个数后比N大的话
        //那么考虑后面的数也都会比N大，不符合要求，直接剪枝
        if(sum + prime[i] <= N)
            dfs(sum + prime[i], i + 1); //选择这个数
        else break;
        //不选这个数的话就是循环到下一个数
    }
}
另： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int ans = 0;
void dfs(int sum, int start)
{
    if(sum == N)
    {
        ans++;
        return;
    }
    if(start == prime.size()) return;
    dfs(sum, start + 1);            //不选这个数
    if(sum + prime[start] <= N)     //选择这个数
        dfs(sum + prime[start], start + 1);

}

记忆化搜索

\(dfs\) 中有两个参数，分别是 \(sum\) 和 \(start\)，我们把这两个参数提取出来，刚好可以作为状态，减少重复性搜索（我们只关心个数而不关心具体是由哪些质数构成的），即：同一个状态搜过了就不要再搜一遍了
避坑：“会不会有大量等于0的，可能要初始化为 \(-1\) ” 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<vector<int> > dp(N+1, vector<int>(320, -1));
//这是用 i+1 来更新i
int dfs(int sum, int start)
{
    //如果被搜过了就直接返回答案
	if(dp[sum][start] != -1) return dp[sum][start];
    //如果sum等于N说明达到了上限
    //从start开始往后的数中，凑出和为 N - sum = 0 的 方案数为1 就是一个都不选
    if(sum == N) return dp[sum][start] = 1;
	int res = 0;
    for(int i = start; i < prime.size(); i++)
    {
        if(sum + prime[i] <= N)
		{   
            //从start开始往后的数中，凑出和为 N-sum 的方案数
            res += dfs(sum + prime[i], i + 1);
		}
        else break;
    }

	return dp[sum][start] = res;
}
cout << dfs(0, 0);
另（就是下面的DP的写法 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//这是用i-1来更新i
int dfs2(int sum, int start)
{
	if(start < 0)   //边界情况（）//防止越界
	{
		if(sum != 0) return 0;
		else return 1;
	}
	if(dp[sum][start] != -1) return dp[sum][start];
    if(sum == 0) return dp[sum][start] = 1;
	int res = 0;
	if(prime[start] <= sum) res = dfs2(sum - prime[start], start - 1);
	res += dfs2(sum, start - 1);
	return dp[sum][start] = res;
}

cout << dfs2(N, prime.size() - 1);

DP

将 \(dfs\) 写成循环结构，也就是常见的 \(dp\) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//f[i][j]: 前i个数中凑出和为j的方案数
vector<vector<int> > f(prime.size(), vector<int>(N + 1, 0));
//初始化，前0个数是2（最小的质数），可以凑出的和是0和2，方案数为1
f[0][2] = f[0][0] = 1;
//从前1个数开始枚举
for(int i = 1; i < prime.size(); i++)
{
    for(int j = 0; j <= N; j++)
    {
        f[i][j] = f[i-1][j];    //不选第i个数
        if(j - prime[i] >= 0)   //选第i个数（这好背包呀（）
            f[i][j] += f[i-1][j - prime[i]];
    }
}

cout << f[prime.size() - 1][N];