递推算法

算法特点：

一个问题的求解需要一系列的计算步骤。如果一个问题，将这个问题中所需要的数据提取出来，可以发现其中的数据之间的关系。那么就找到的递推公式，就可以编程序解决问题啦
思考的时候，如果发现正着找规律不合理，就试试倒着推。

典型例子

斐波那契额数列：1 1 2 3 5 8 13 …即前两项是1，之后的某一项=前两项之和f(n)=f(n-1)+f(n-2) n>=3

• 大家肯定都知道斐波那契数列，把这个数列拿出来，咱们都能找到其中的规律。但是如果换成其他的实际问题，就很容易做不出来。

比如说

例题1

• 分析
  我们用R表示成熟的兔子，r表示新兔子。将前六项列出来如下：
  !
  我们可以发现，这就是一个斐波那契数列。
  小细节：在列举式，因为兔子分为两种情况。打兔子和小兔子，所以可以用大小写来表示，简单明了

#include <bits/stdc++.h>
using namespace std;
int Fibonacc(int n)
{
    int a[100];
    a[1] = 1;
    a[2] = 1;
    if (n >= 3)
    {
        for (int i = 3; i <= n; i++)
        {
            a[i] = a[i - 1] + a[i - 2];
        }
    }

    return a[n];
}
int main()
{

    int num;
    cin >> num;
    int sum = Fibonacc(num);
    cout << sum << endl;
}

例题2
这也是斐波那契数列

楼梯有n个台阶，上楼可以一步上一阶，也可以一步上两阶。一共有多少种上楼的方法？

当然

斐波那契额数列只是其中的一种，地推关键在于“推”。我们要拿出小学时找规律的乐趣来做这种题（哈哈哈，其实小学找规律很简单，但是遇到这种题我总是找不到，尴尬????）
例题

思路：
如果按照题目，从第一个开始，就会发现：有两条路，每一条路后面的路会打不一样。比如说第一次我们选择8，但是可能8后面的数都很小，这样就找不到正确结果。所以我们倒着试试。
假设我们走到了倒数第二行，不一定是哪一个数，但是倒数第二行每一个数都会有两种情况选择，而且我们会选择较大的数。那么倒数第二行的书就确定了。最后一行别可以丢掉。以此类推，最后到第一行，就只有一个数，也就是最大的数。

#include <bits/stdc++.h>
using namespace std;
int a[101][101];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
         cin>>a[i][j];
    }

    for(int p=n-1;p>=1;p--)
    {
        for(int q=1;q<=n;q++)
        {
            int r1,r2;
            r1=a[p][q]+a[p+1][q];
            r2=a[p][q]+a[p+1][q+1];
            if(r1>r2)
            a[p][q]=r1;
            else
            {
                a[p][q]=r2;
            }
            
        }
    }

    cout<<a[1][1];
}