7 递推

递推算法：即通过已知条件，利用特定关系得出中间推论，直到得到结果的算法。地推算法分为顺推和逆推两种。

顺推法：所谓顺推法是从已知条件出发，逐步推算出要解决的问题。如斐波那契数列，设他的函数为f（n），已知f（1）=1，f（2）=1；f（n）=f（n-2）+f（n-1）（n>=3),则我们通过顺推可以知道f（3）=f（1）+f（2）=2，f（4）=f（2）+f（3）=3……直至我们要求得解。

逆推法：所谓逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程。

递推算法的经典例子：

【案例】顺推法：从原点出发，一步只能向右走，向上走或向左走。不能向后走，走过的点塌陷，恰好走n步共有多少种走法？

题目链接：http://acm.hrbust.edu.cn/vj/index.php?c=problem-problem&id=200194

样例输入：n=2

样例输出：result=7

样例输入：n=3

样例输出：result=17

解题思路：要解决走n步共有多少种走法，我们在拿到题目的时候最直接的想法就是先画出当n=1，n=2，n=3。。。。n=N时对应走法的案例，有简单到复杂，有特殊到一般的推理过程，找出规律获得解题思路。在数学上，我们称为归纳法。如果用编程的方法来求解，我们把这样的求解思路（算法）称之为递推法。递推的精髓在于f（n）的结果一般由f（n-1），f（n-2）……f（n-k）的前k次结果推导出来。我们在解决这类递推问题时，难点就是如何从简单而特殊的案例，找到问题的一般规律。

下面是这道题的心得，供大家参考：

1）当n=1时，绘出走法图

共有3种不同的走法即f（1）=3

2）当n=2时，绘出走法图

共有7种不同的走法即f（2）=7

3）当n=3时，绘出走法图

共有17种走法即f（3）=17

由此我们不难看出，对于任何一个起点，最多可以走出3种走法，但最少必须走出2种走法，那么我们要求出f（n），实际上转换为如果我们得到上一步即f（n-1）有多少个终点是有3种走法的，有多少个点是有2种走法的，那么问题就解决了。

a上一步，即f（n-1）是有多少终点有3种走法的

对于n=3时，f（2）有3个点可以走出3种不同的走法，这3个点是怎么得到的呢？他与n值有没有联系呢？如果f（1），即上上部存在，那么从上上步出发的线路里面必然会有一条向上走的线路，而这条线路在到达f（2）之后，向f（3）出发也必然有左上右这3种走法，那么我们就得出结论：f（3）=3*f（1）+2*（f（2）-f（1））

b.得出f（n）的一般关系式

f（n）=3*f（n-2）+2*（f（n-1）-f（n-2））（n>=3)

化简：f（n）=2*f(n-1)+f(n-2)  (n>=3)

#include<cstdio>
#include<cstring>
#include<iostream>
int f[30];
using namespace std;
int main ()
{
    f[1]=3;f[2]=7;
    for(int i=3;i<=20;i++){
        f[i]=3*f[i-2]+2*(f[i-1]-f[i-2]);
    }
     int t,n;
     cin>>t;
     while(t--){
        cin>>n;
        cout<<f[n]<<endl;
     }
}

逆推法：是从已知的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。

父亲准备为小龙的四年大学生活一次性储蓄一笔钱，使用整存零取的方式，控制小龙每月月底取1000元准备下月使用。假设1银行一年整存零取的年息为1.71%，请算出父亲至少需要存入多少钱才行。

若在第48月小龙大学毕业时连本带息要取1000元，则要先求出第47个月末时银行的存款（包括利息）的钱数

第47月月末存款=1000/（1+0.0171/12）

第46月月末存款=（第47月月末存款+1000）/（1+0.0171/12）

第45月月末存款=（第46月月末存款+1000）/（1+0.0171/12）

此次类推，可以求出第1月月末存款，因为第第1月月末存款是经过了1个月的时间，所以父亲最后存入的钱数=第1月月末存款/（1+0.0171/12）