所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。
从已知条件出发逐步推到问题结果，此种方法叫顺推。
从问题出发逐步推到已知条件，此种方法叫逆推。
无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。

算法特点：

• 1.问题可以划分成多个状态；
  2.除初始状态外，其它各个状态都可以用固定的递推关系式来表示。
  在我们实际解题中，题目不会直接给出递推关系式，而是需要通过分析各种状态，找出递推关系式。

例题1：树塔问题

描述：

树塔问题，编写程序计算从顶到底的某处的一条路径，使该路径所途径的数字最大

#include<bits/stdc++.h>
using namespace std;
int main() {int n, a[101][101];cin >> n;int sum =0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {cin >> a[i][j];}
}for (int i = n; i >= 1; i--) {int max = a[i][1];for (int j = 1; j <= i; j++) {if (a[i][j] > max) {max = a[i][j];}}sum += max;}cout << sum << endl;return 0;
}

---

例题2：斐波那契数列第N项

#include<bits/stdc++.h>
using namespace std;
int main() {int f0 = 1, f1 = 1, f2,n;cin >> n;for (int i = 3; i <= n; i++) {af2 = f1 + f0;f0 = f1;f1 = f2;}cout << f2;return 0;
}

---

例题3：昆虫繁殖

描述

科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过x个月产卵)，问过z个月以后，共有成虫多少对？0≤x≤20,1≤y≤20,X≤z≤50

#include <iostream>
using namespace std;
#include <cstdio>
int a[25], b[25];
void fun(int x,int y,int z)
{a[1] = 1; b[1] = 0;for (int i = 1; i <= x; i++){a[i] = 1;b[i] = 0;}for (int i = x + 1; i <= z+1; i++)　{：a[i] = a[i - 1] + b[i - 2];b[i] = a[i - x] * y;   　}cout << a[z+1];
}
int main()
{int x, y, z;cin >> x >> y >> z;fun(x,y,z);
}

---

例题4：位数问题

描述

在所有的 N 位数中，有多少个数中有偶数个数字 3？由于结果可能很大，你只需要输出这个答案对 12345 取余的值。

#include<bits/stdc++.h>
using namespace std;
bool is_even(int a) {int count = 0;while (a != 0) {int ge = a % 10;if (ge == 3) { count++; }a /= 10;}if (count % 2 == 0) {return true;}else {return false;}
}
int main() {int n;cin >> n;int count = 0;for (int i = pow(10,n-1); i <= pow(10, n) - 1; i++) {if (is_even(i)) {count++;}}cout << count % 12345 << endl;return 0;
}

---

五种递推问题：

·Fibonacci数列

·Hanoi塔问题

·平面分割问题

·Catalan数

·第二类Stirling数

---

习题：

1.上台阶

楼梯有n(71>n>0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算共有多少种不同的走法。

#include<cstdio>  
long long d[100]= {0};  
int main()
{  d[1]=1;d[2]=2;d[3]=4;  for(int i=4; i<=100; i++)d[i]=d[i-1]+d[i-2]+d[i-3];  int a;  while(scanf("%d",&a)==1&&a)   printf("%lld\n",d[a]);  return 0;  
}  

---

2.流感传染

有一批易感人群住在网格状的宿舍区内，宿舍区为n*n的矩阵，每个格点为一个房间，房间里可能住人，也可能空着。在第一天，有些房间里的人得了流感，以后每天，得流感的人会使其邻居传染上流感，（已经得病的不变），空房间不会传染。请输出第m天得流感的人数。

第一行一个数字n，n不超过100，表示有n*n的宿舍房间。

接下来的n行，每行n个字符，’.’表示第一天该房间住着健康的人，’#’表示该房间空着，’@’表示第一天该房间住着得流感的人。

接下来的一行是一个整数m，m不超过100。

#include<bits/stdc++.h>
using namespace std;
char a[101][101]
int main() {int n,day,count=0;cin >> n;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cin >> a[i][j];}}cin >> day;for (int i = 2; i <= day; i++) {for (int j = 1; j <= n; j++) {for (int k = 1; k <= n; k++) {if (a[j][k] == '@') {if (a[j][k + 1] == '.') {a[j][k + 1] = '!';}if (a[j][k -1] == '.') {a[j][k -1] = '!';}if (a[j+1][k] == '.') {a[j+1][k] = '!';}if (a[j-1][k] == '.') {a[j-1][k] = '!';}}}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (a[i][j] == '!') {a[i][j] = '@';}}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cout << a[i][j] << " ";}cout << endl;}cout << endl;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (a[i][j] == '@') {count++;}}}cout << endl;cout << count;return 0;
}

---

*3.山区建小学

政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di(为正整数)，其中，0<i<m。为了提高山区的文化素质，政府又决定从m个村中选择n个村建小学(设0<n≤m<500)。请根据给定的m、n以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。

第1行为m和n，其间用空格间隔

第2行为m−1个整数，依次表示从一端到另一端的相邻村庄的距离，整数之间以空格间隔。

#include<bits/stdc++.h>
using namespace std;
int dis[100][100], dp[100][100], d[100];
//dis两村庄中建立一所学校的最小距离
//d村庄到原点的距离
//dp最小距离
int cal(int x, int y) {int mid = (x + y) / 2,ans = 0;for (int i = x; i <= y; i++) {ans += abs(d[i] - d[mid]);}return ans;
}
int min(int x, int y) {return x > y ? y : x;
}
int main() {int m, n;cin >> m >> n;for (int i = 2; i <= m; i++) {cin >> d[i];d[i] += d[i - 1];}//建立一所学校for (int i = 1; i <= m; i++) {for (int j = i; j <= m; j++) {dis[i][j] = cal(i, j);}}//建立n所学校for (int i = 1; i <= m; i++) {for (int j = 1; j <= n && j<=i; j++) {dp[i][j] = 999999;for(int k =1;k<i;k++){if (j == 1) { dp[i][j] = dis[1][i]; }else{dp[i][j] = min(dp[i][j], dp[k][j-1] + dis[k+1][i]);}}}}cout << dp[m][n];return 0;
}