递推算法C++

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

算法特点：

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

  例题1：树塔问题

  描述：

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

  #include
  using namespace std;
  int main() {
  	int n, a[101][101];
  	cin >> n;
  	int sum =0;
  	for (int i = 1; i  a[i][j];
  		}
  }
  		for (int i = n; i >= 1; i--) {
  			int max = a[i][1];
  			for (int j = 1; j  max) {
  					max = a[i][j];
  				}
  			}
  			sum += max;
  		}
  	
  		cout  n;
  	for (int i = 3; i > z;
         fun(x,y,z);
  }

  ---

  例题4：位数问题

  描述

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

  #include
  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  n;
  	for (int i = 1; i  a[i][j];
  		}
  	}
  	cin >> day;
  	for (int i = 2; i