动态规划（题目提升）

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

方法二：动态规划

想了很久 没想出来

原文地址：https://blog.csdn.net/2301_80454352/article/details/136353492

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！