将算式的计算结果存储在内存中,在需要的时候直接调用这个结果,从而避免无用的重复计算,就能提高处理效率。动态规划就是属于这类的手法。
之前有这样一道递归的穷举搜索题:
题号: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;
}
}