【记忆化搜索入门】(例题：递归求组合数加强版本)

什么是记忆化搜索呢？搜索的低效在于没有能够很好地处理重叠子问题；动态规划虽然比较好地处理了重叠子问题，但是在有些拓扑关系比较复杂的题目面前，又显得无奈。记忆化搜索正是在这样的情况下产生的，它采用搜索的形式和动态规划中递推的思想将这两种方法有机地综合在一起，扬长避短，简单实用，在信息学中有着重要的作用。

用一个公式简单地说：记忆化搜索=搜索的形式+动态规划的思想。

1.记忆化搜索的基本思想
记忆化搜索的思想是,在搜索过程中，会有很多重复计算,如果我们能记录一些状态的答案，就可以减少重复搜索量
2、记忆化搜索是类似于动态规划的，不同的是，它是倒做的“递归式动态规划”。

其实，记忆化搜索的核心，就在于搜索的时候是否记录已经算出的值，记录之后就可以在以后的搜索中直接调用，可以节省很多的时间，能够有效地优化程序。
下面贴一道简单的题目：

递归求组合数加强版本
Description
编一递归程序，求组合数   C(n,m)   
已知  C(n,m)=C(n-1,m)+C(n-1,m-1);
Input
一行两个数字N,M,其值小于等于5000
Output
方案数%1000000007

Sample Input
1 1
Sample Output
1 
HINT
普通递归写不出哦

首先，如果不用记忆化搜索，直接用递归来解决或者是套公式的话是试不出的。
注：公式【记忆化搜索入门】(例题：递归求组合数加强版本)
那么就只能考虑记忆化搜索（手动滑稽）
所以我们要用一个数组来记忆已经算出的答案：`int f[5001][5001];
边界

if(m==1)return n;
if(n==m)return 1;

记忆化

if(f[n][m]>0)return f[n][m];
return f[n][m]=(C(n-1,m)+C(n-1,m-1))%MOD;

代码：

#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int f[5001][5001];
long long C(int n,int m)
{
	if(m==1)return n;
	if(n==m)return 1;
	if(f[n][m]>0)return f[n][m];
	return f[n][m]=(C(n-1,m)+C(n-1,m-1))%MOD;
}
int main()
{
	int n,m;
	cin>>n>>m;
	cout<<C(n,m)<<endl;
	return 0;
}

ov.

【记忆化搜索入门】(例题：递归求组合数加强版本)

相关推荐