动态规划（题目提升）

[NOIP2012 普及组] 摆花

方法一：记忆化搜索

何为记忆化搜素：就是使用递归函数对每次得到的结果进行保存，下次遇到就直接输出即可

那么这个题目使用递归（DFS）是怎样的？
首先我们需要搞清楚几个坑点：1.不是所有的花都要取到，只要我们取到的花的数量满足题目给的要求就可以了。 2.我们使用递归函数的时候需要使用一个变量step来代表我们所选择的花的种类，然后还需要一个变量来代表我们已经选的花的数量即可，先用void类型来写一遍这个函数

#include<iostream>
using namespace std;
int a[100000];
int n,m;
int ans=0;
void dfs(int step,int sum)
{if(step>n){if(sum==m){ans++;return ;}return ;}for(int i=0;i<=a[step];i++){dfs(step+1,sum+i);}return ;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];dfs(1,0);cout<<ans<<endl;return 0;
}

使用void类型来书写的函数的好处就是方便理解，但是这样就是用不了记忆化搜索

所以再用int类型来书写一遍dfs函数

#include<iostream>
using namespace std;
const int N=10000,mod = 1000007;
int a[100000];
int n,m;
int vis[N][N];
int dfs(int step,int sum)
{if(sum>m)return 0;if(sum==m)//终止条件只能是这一个，后面的花可以没有被种return 1;if(step==n+1)//如果种类已经查过了最大种类，那么就不能继续搜索return 0;//if(vis[step][sum])//如果已经查过了，那么就不需要查了直接返回//return vis[step][sum];int ans=0;//for(int i=0;i<=a[step];i++){ans=(dfs(step+1,sum+i)+ans)%mod;}//vis[step][sum]=ans;return ans;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];cout<<dfs(1,0)<<endl;return 0;
}

记忆化就是在其中加上数组用于保存数据

#include<iostream>
using namespace std;
const int N=10000,mod = 1000007;
int a[100000];
int n,m;
int vis[N][N];
int dfs(int step,int sum)
{if(sum>m)return 0;if(sum==m)//终止条件只能是这一个，后面的花可以没有被种return 1;if(step==n+1)//如果种类已经查过了最大种类，那么就不能继续搜索return 0;if(vis[step][sum])//如果已经查过了，那么就不需要查了直接返回return vis[step][sum];int ans=0;//这个ans变量一定要放在dfs函数内部for(int i=0;i<=a[step];i++){ans=(dfs(step+1,sum+i)+ans)%mod;}vis[step][sum]=ans;return ans;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];cout<<dfs(1,0)<<endl;return 0;
}