体积(C++)[递归][记忆化]

体积(C++)[递归][记忆化] 前言：

最近，由于学习原因，没有更新了（其实就是忘了），所以近期打算讲讲记忆化的题。

题目： Description

给出 n 件物品，每件物品有一个体积 V i ，求从中取出若干件物品能够组成的不同的体积和有多少种可能。

Format Input

第 1 行 1 个正整数，表示 n。

第 2 行 n 个正整数，表示 V i ，每两个数之间用一个空格隔开。

n小于等于20，总体积小于等于1000

Output

一行一个数，表示不同的体积和有多少种可能。

Samples

【输入样例】

输入数据 1

3 
1 3 4

Copy

输出数据 1

6

Copy

【输出样例】

Limitation

1s, 1024KiB for each test case.

 分析：

首先，我们可以用递归来做这道题，思路如下：

每个数我们可以选择加或者不加，

但是和有可能会重复，

so，加个记忆化就行了。

奉上代码：

#include 
using namespace std;
int a[21], n;
bool b[1000000];//记忆化，如果b[i]为0（假），则代表i没出现过，为1（真）代表出现过。 
int ans = 0;
void dfs(int dep, int sum) {//dep，深度；sum，和。 
    if (dep == n + 1) {//记忆化 
        if(!b[sum]&&sum)
        {
        	b[sum] = true;
        	ans++;
		}
        return ;
    }
    dfs(dep + 1, sum + a[dep]); //递归下一深度，和加a[dep]。 
    dfs(dep + 1, sum);//递归下一深度，和不变 
}
int main() {
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    dfs(1, 0);
   


    cout << ans << endl;

    return 0;
}