【题解】动态规划法实现穷举搜索（ALDS1_5_A）

Exhaustive Search
Write a program which reads a sequence A of n elements and an integer M, and outputs "yes" if you can make M by adding elements in A, otherwise "no". You can use an element only once.

You are given the sequence A and q questions where each question contains Mi.

Input
In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers (Mi) are given.

Output
For each question Mi, print yes or no.

Constraints
n ≤ 20
q ≤ 200
1 ≤ elements in A ≤ 2000
1 ≤ Mi ≤ 2000

5
1 5 7 10 21
8
2 4 17 8 22 21 100 35

no
no
yes
yes
yes
yes
no
no

#include<iostream>
using namespace std;

bool dp[2001][2001];
int n;
int a[2005];
bool solve(int i,int m)
{
    if(dp[i][m])
        return dp[i][m];
    if(m==0) return true;
    if(i>=n) return false;
    dp[i][m] = solve(i+1,m)||solve(i+1, m-a[i]);
    return dp[i][m];

}


int main()
{

    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int q;
    int m;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        cin>>m;
        cout<<(solve(0,m)?"yes":"no")<<endl;
    }



}