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

将算式的计算结果存储在内存中，在需要的时候直接调用这个结果，从而避免无用的重复计算，就能提高处理效率。动态规划就是属于这类的手法。

之前有这样一道递归的穷举搜索题：

题号：ALDS1_5_A

来自 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=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

这道题的思路就是定义一个solve(i,m)递归函数，然后来决定选或不选第i个元素。选的话就solve(i+1,m-A[i])，不选就直接solve(i+1,m)。如果当遍历完整个数组A之后，m为0，那么就说明这个数组里存在几个元素相加等于输入的m。

但是我们会发现这个计算十分缓慢，分析会发现，其实是做了很多无用的重复计算。我们只需要把已经计算过的值记录下来，就能在下一次进行相同计算的时候，直接调用之前计算的结果。这将会大大加快我们的计算速度。

我们可以设计一个数组bool dp[i][m]来存储这个计算结果。每一位存储的就是当i、m取相应的值的时候，能否实现剩余的元素相加等于m。

那么有了这个思路，就能利用动态规划法把上面这个穷举搜索的问题进行提速。

#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;
    }



}

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~