递推求解
标签: 机试攻略 - 高分篇
学习人数: 19.9k


高清播放
赞赏支持

首先,什么是动态规划?

  动态规划是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。其实就是分解问题,分而治之。可能这样说大家都不太理解,其实这个有点类似于数学中的递推公式。来举一个简单的例子,看下边这个题:

 

N阶楼梯上楼问题:一次可以走两阶或一阶,问有多少种上楼方式。

这就是动态规划最简单的一个列子。拿到这个题,大家是不是都有点迷,这个到底怎么做?

是不是没有思路,那么按照动态规划思想,我们可以先分析下问题,每次都有两种跳法,分别是一阶或者两阶,那么如果当前是第n个台阶,那么跳法是不是是(n-1)台阶的跳法数加上(n-2)台阶的跳法数?

如果划算成公式是F(n) =  F(n-1)+F(n-2)。

F(n)代表第n阶台阶的跳法的数量。这不就相当于找到了一个递推公式,然后来进行计算。

 

N阶楼梯上楼问题
题目描述:

N阶楼梯上楼问题:一次可以走两阶或一阶,问有多少种上楼方式。(要求采用非递归)
输入描述:
输入包括一个整数N,(1<=N<90)。
输出描述:
可能有多组测试数据,对于每组数据,
输出当楼梯阶数是N时的上楼方式个数。
输入样例#:
4
输出样例#:
5
题目来源:
DreamJudge 1413

题目解析:根据上面的分析得出公式F(n) =  F(n-1)+F(n-2),然后递推即可。

 

参考代码

#include <stdio.h>  
  
int main() {  
    int i,N;  
    long long a[90];  
    while(scanf("%d",&N) != EOF) {  
        a[1]=1;  
        a[2]=2;  
        for(i=3;i<=N;i++)  
            a[i]=a[i-1]+a[i-2];  
        printf("%lld\n",a[N]);  
    }  
    return 0;  
}  


 

登录查看完整内容


课后作业

练习题目

DreamJudge 1197 吃糖果
DreamJudge 1033 细菌的繁殖


登录后开始许愿

暂无评论,来抢沙发