【算法教程】【C/C++】递推——程序设计思路与代码实现

faryou3个月前 (07-07)技术教程

前言

        在算法中,递推是一种重要的方法。通过列出递推式,我们可以解决许多棘手的问题。


“状态”

        在算法中,状态是指某个变量在某种特定情况下的值。例如当i>=0时,abs(i)==i;而当i<=0时,abs(i)==-i。如果我们把这里的abs(i)赋值给一个变量j,那么这个变量j的状态(值)就随着i的变化而变化。

        就上面这个例子,我们可以列出关于j的状态转移方程:当i>=0时,j[i]=i;当i<=j时,j[i]=-i。


程序设计思路

        在解决具有嵌套性质的问题时,尤其是当n的值不同,且各个答案之间有关联的问题时,列出一个正确的递推式,就几乎等于解决了问题,不必进行暴力搜索等操作。

        由于直接讲解比较抽象,所以我们直接来看题目。


代码实现

R-C.png

        可以看到,这道题要求我们计算走楼梯的步数。很显然,如果我们使用搜索来解题,那么速度将会偏慢,导致TLE。所以,这里我们使用递推来解决问题。

        由题意,可知走到第x个台阶,一定是从第i-1个台阶或从第i-2个台阶出发。由此,我们可以列出方程:f[x]=f[x-1]+f[x-2](f[x]表示走到第x个台阶的方案总数)。

        列出方程后,我们只需要找到这个方程的初始状态就可以求解了。而不难看出f[1]=1,f[2]=2。问题解决!

        你以为这就完了?No!注意数据没有范围,要用高精度!!!(如果不知道怎么用高精度的可参考:https://blog.faryou.eu.org/post/98.html

        代码如下:

#include <bits/stdc++.h>
using namespace std;

int a[5010][5000],len=1,n;//a相当于上文中的f(高精度所以用二维),len存储位数,n见题意

void add(int arr){
	for(int i=1;i<=len;i++) a[arr][i]=a[arr-1][i]+a[arr-2][i];//高精度一位一位加
	for(int i=1;i<=len;i++) if(a[arr][i]>=10){//进位
		a[arr][i+1]+=a[arr][i]/10;
		a[arr][i]%=10;
	}
	if(a[arr][len+1]>0) len++;//位数++
	return ;
}

int main(){
	scanf("%d",&n);
	a[0][1]=1;//初始值,因为f[2]=2=f[1]+1
	a[1][1]=1;
	for(int i=2;i<=n;i++) add(i);//重复计算
	for(int i=len;i>0;i--) printf("%d",a[n][i]);
	return 0;
}


结语

        递推是一个极为重要的方法,后面要学习的DP(动态规划)本质上就是分类讨论列出不同情况下的状态转移方程。我是faryou,下次见!

本文链接:https://blog.faryou.eu.org/post/104.html 转载需经作者授权!

分享到:

扫描二维码推送至手机访问。

版权声明:本文由faryou的博客发布,如需转载请注明出处。

本文链接:https://blog.faryou.eu.org/post/104.html

标签: C++算法基础
分享给朋友:

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。